“Near-Regular Structure Discovery Using Linear Programming” by Huang, Guibas and Mitra

  • ©

Conference:


Type(s):


Title:

    Near-Regular Structure Discovery Using Linear Programming

Session/Category Title:   Shape Analysis

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    Near-regular structures are common in manmade and natural objects. Algorithmic detection of such regularity greatly facilitates our understanding of shape structures, leads to compact encoding of input geometries, and enables efficient generation and manipulation of complex patterns on both acquired and synthesized objects. Such regularity manifests itself both in the repetition of certain geometric elements, as well as in the structured arrangement of the elements. We cast the regularity detection problem as an optimization and efficiently solve it using linear programming techniques. Our optimization has a discrete aspect, that is, the connectivity relationships among the elements, as well as a continuous aspect, namely the locations of the elements of interest. Both these aspects are captured by our near-regular structure extraction framework, which alternates between discrete and continuous optimizations. We demonstrate the effectiveness of our framework on a variety of problems including near-regular structure extraction, structure-preserving pattern manipulation, and markerless correspondence detection. Robustness results with respect to geometric and topological noise are presented on synthesized, real-world, and also benchmark datasets.

References:


    1. D. Anguelov, P. Srinivasan, D. Koller, S. Thrun, J. Rodgers, and J. Davis. 2005. Scape: Shape completion and animation of people. In ACM SIGGRAPH Papers. 408–416.
    2. A. Berner, M. Wand, N. J. Mitra, D. Mewes, and H.-P. Seidel. 2011. Shape analysis with subspace symmetries. Comput. Graph. Forum 30, 2, 277–286.
    3. M. Bokeloh, M. Wand, and H.-P. Seidel. 2010. A connection between partial symmetry and inverse procedural modeling. In ACM SIGGRAPH Papers. 104:1–104:10.
    4. S. Boyd and L. Vandenberghe. 2004. Convex Optimization. Cambridge University Press, Cambridge, UK.
    5. A. Bronstein, M. Bronstein, and R. Kimmel. 2008. Numerical Geometry of Non-Rigid Shapes 1st Ed. Springer.
    6. Y. Chen and G. Medioni. 1992. Object modelling by registration ofn multiple range images. Image Vis. Comput. 10, 145–155.
    7. H. Edelsbrunner and J. Harer. 2010. Computational Topology: An Introduction. American Mathematical Society.
    8. M. S. Floater. 2003. Mean value coordinates. Comput.-Aid. Geom. Des. 20, 1, 19–27.
    9. R. Gal, O. Sorkine, N. J. Mitra, and D. Cohen-Or. 2009. Iwires: An analyze-and-edit approach to shape manipulation. In ACM SIGGRAPH Papers. 33:1–33:10.
    10. D. Giorgi, S. Biasotti, and L. Paraboschi. 2007. Shape retrieval contest 2007: Watertight models track. http://watertight.ge.imati.cnr.it/watertight-global.pdf.
    11. M. Grant and S. Boyd. 2011. CVX: Matlab software for disciplined convex programming. http://www.stanford.edu/-boyd/cvx/.
    12. J. Hays, M. Leordeanu, A. A. Efros, and Y. Liu. 2006. Discovering texture regularity as a higher-order correspondence problem. In Proceedings of the European Conference on Computer Vision Part II. 522–535.
    13. M. Kilian, N. J. Mitra, and H. Pottmann. 2007. Geometric modeling in shape space. In ACM SIGGRAPH Papers. 64:1–64:9.
    14. V. G. Kim, Y. Lipman, X. Chen, and T. A. Funkhouser. 2010. Mobius transformations for global intrinsic symmetry analysis. Comput. Graph. Forum 29, 5, 1689–1700.
    15. S. Krishnan, P. Y. Lee, J. B. Moore, and S. Venkatasubramanian. 2005. Global registration of multiple 3d point sets via optimization-on-a-manifold. In Proceedings of the Symposium on Geometry Processing (SGP’05).
    16. M. Li, F. C. Langbein, and R. R. Martin. 2006. Constructing regularity feature trees for solid models. In Proceedings of the Conference on Geometric Modeling and Processing. Springer, 267–286.
    17. Y. Lipman and T. Funkhouser. 2009. Mobius voting for surface correspondence. In ACM SIGGRAPH Papers. 72:1–72:12.
    18. S. Liu, R. R. Martin, F. C. Langbein, and P. L. Rosin. 2007. Segmenting periodic reliefs on triangle meshes. In Proceedings of the IMA Conference on the Mathematics of Surfaces. 290–306.
    19. Y. Liu, W.-C. Lin, and J. Hays. 2004. Near-regular texture analysis and manipulation. In ACM SIGGRAPH Papers. 368–376.
    20. N. J. Mitra, A. M. Bronstein, and M. M. Bronstein. 2010. Intrinsic regularity detection in 3d geometry. In Proceedings of the European Conference on Computer Vision Part III. 398–410.
    21. N. J. Mitra, L. J. Guibas, and M. Pauly. 2006. Partial and approximate symmetry detection for 3d geometry. In ACM SIGGRAPH Papers. 560–568.
    22. N. J. Mitra, M. Pauly, M. Wand, and D. Ceylan. 2012. Symmetry in 3d geometry: Extraction and applications. In Eurographics State-of-the-Art Report.
    23. N. J. Mitra, M. Wand, H. Zhang, D. Cohen-Or, and M. Bokeloh. 2013. Structure-aware shape processing. In Eurographics State-of-the-Art Report.
    24. M. Ovsianikov, Q. Merigot, F. Memoli, and L. J. Guibas. 2010. One point isometric matching with the heat kernel. Comput. Graph. Forum 29, 5, 1555–1564.
    25. M. Ovsianikov, J. Sun, and L. J. Guibas, 2008. Global intrinsic symmetries of shapes. Comput. Graph. Forum 27, 5, 1341–1348.
    26. M. Park, K. Brocklehurst, R. T. Collins, and Y. Liu. 2009. Deformed lattice detection in real-world images using mean-shift belief propagation. IEEE Trans. Pattern Anal. Mach. Intell. 31, 1804–1816.
    27. M. Pauly, N. J. Mitra, J. Wallner, H. Pottmann, and L. J. Guibas. 2008. Discovering structural regularity in 3d geometry. In ACM SIGGRAPH Papers. 43:1–43:11.
    28. J. Podolak, P. Shilane, A. Golovinskiy, S. Rusinkiewicz, and T. Funkhouser. 2006. A planar-reflective symmetry transform for 3d shapes. In ACM SIGGRAPH Papers. 549–559.
    29. N. Ray, W. C. Li, B. Levy, A. Sheifer, and P. Alliez, 2006. Periodic global parameterization. ACM Trans. Graph. 25, 1460–1485.
    30. F. Schaffalitzky and A. Zisserman. 1999. Geometric grouping of repeated elements within images. In Shape, Contour and Grouping in Computer Vision, Springer, 165–181.
    31. A. Schrijver. 1986. Theory of Linear and Integer Programming. John Wiley & Sons, New York.
    32. O. Sorkine, D. Cohen-Or, Y. Lipman, M. Alexa, C. Rossl, and H.-P. Seidel. 2004. Laplacian surface editing. In Proceedings of the Symposium on Geometry Processing (SGP’04). 175–184.
    33. J. Sun, M. Ovsianikov, and L. Guibas. 2009. A concise and provably informative multi-scale signature based on heat diffusion. In Proceedings of the Symposium on Geometry Processing (SGP’09). 1383–1392.
    34. A. Tevs, M. Bokeloh, M. Wand, A. Schilling, and H.-P. Seidel. 2009. Isometric registration of ambiguous and partial data. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR’09). 1185–1192.
    35. D. W. Thompson. 1945. On Growth and Form. Cambridge University Press, Cambridge, UK.
    36. T. Tuytelaars, A. Turina, and L. van Gool. 2003. Noncombinatorial detection of regular repetitions under perspective skew. IEEE Trans. Pattern Anal. Mach. Intell. 25, 418–432.
    37. O. van Kaick, H. Zhang, C. Hamarneh, and D. Cohen-Or. 2011. A survey on shape correspondence. Comput. Graph. Forum 30, 6, 1681–1707.
    38. M. Wand, P. Jenke, Q. Huang, M. Bokeloh, L. Guibas, and A. Schilling. 2007. Reconstruction of deforming geometry from time-varying point clouds. In Proceedings of the Symposium on Geometry Processing (SGP’07). 49–58.
    39. S.-Q. Xin and G.-J. Wang. 2009. Improving chen and han’s algorithm on the discrete geodesic problem. ACM Trans. Graph. 28, 104:1–104:8.
    40. K. Xu, H. Zhang, A. Tagliasacchi, L. Liu, C. Li, M. Meng, and Y. Xiong. 2009. Partial intrinsic reflectional symmetry of 3d shapes. In ACM SIGGRAPH Asia Papers. 138:1–138:10.

ACM Digital Library Publication:


Overview Page: