“Discovering structural regularity in 3D geometry” by Pauly, Mitra, Wallner, Pottmann and Guibas

We introduce a computational framework for discovering regular or repeated geometric structures in 3D shapes. We describe and classify possible regular structures and present an effective algorithm for detecting such repeated geometric patterns in point- or meshbased models. Our method assumes no prior knowledge of the geometry or spatial location of the individual elements that define the pattern. Structure discovery is made possible by a careful analysis of pairwise similarity transformations that reveals prominent lattice structures in a suitable model of transformation space. We introduce an optimization method for detecting such uniform grids specifically designed to deal with outliers and missing elements. This yields a robust algorithm that successfully discovers complex regular structures amidst clutter, noise, and missing geometry. The accuracy of the extracted generating transformations is further improved using a novel simultaneous registration method in the spatial domain. We demonstrate the effectiveness of our algorithm on a variety of examples and show applications to compression, model repair, and geometry synthesis.

1. Blakemore, C., and Campbell, F. 1969. On the existence of neurones in the human visual system selectively sensitive to the orientation and size of retinal images. J. Physiol. 203, 237–260.Google ScholarCross Ref
2. Brown, J. C. 1991. Calculation of a constant Q spectral transform. J. Acoust. Soc. Am. 80, 425–434.Google ScholarCross Ref
3. Buades, A., Coll, B., and Morel, J.-M. 2008. Nonlocal image and movie denoising. Int. J. Computer Vision 76, 2, 123–139. Google ScholarDigital Library
4. Cazals, F., and Pouget, M. 2003. Estimating differential quantities using polynomial fitting of osculating jets. In Proc. Symp. Geometry Processing. 177–187. Google ScholarDigital Library
5. Comaniciu, D., and Meer, P. 2002. Mean shift: A robust approach toward feature space analysis. IEEE Trans. PAMI 24, 5, 603–619. Google ScholarDigital Library
6. Fischler, M., and Bolles, R. 1981. Random Sample Consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM, 381–395. Google ScholarDigital Library
7. Golovinskiy, A., Podolak, J., and Funkhouser, T. 2007. Symmetry-aware mesh processing. Tech. Rep. 782–07, Princeton Univ.Google Scholar
8. Grünbaum, B., and Shephard, G. C. 1987. Tilings and Patterns. W. H. Freeman.Google Scholar
9. Hall, B. C. 2003. Lie Groups, Lie algebras, and representations. An Elementary Introduction. Springer.Google Scholar
10. Hofer, M., Odehnal, B., Pottmann, H., Steiner, T., and Wallner, J. 2005. 3D shape recognition and reconstruction based on line element geometry. In Int. Conference on Computer Vision. 1532–1538. Google ScholarDigital Library
11. Horn, B. K. P. 1987. Closed form solution of absolute orientation using unit quaternions. J. Opt. Soc. A 4, 629–642.Google ScholarCross Ref
12. Hsu, J. T., Liu, L.-C., and Li, C. 2001. Determination of structure component in image texture using wavelet analysis. In Int. Conference on Image Processing, 166–169.Google Scholar
13. Jacquin, A. 1992. Image coding based on a fractal theory of iterated contractive image transformations. IEEE Trans. Image Proc. 1, 1, 18–30.Google ScholarDigital Library
14. Korah, T., and Rasmussen, C. 2007. 2D lattice extraction from structured environments. In Int. Conference on Image Processing, 61–64.Google Scholar
15. Leung, T. K., and Malik, J. 1996. Detecting, localizing and grouping repeated scene elements from an image. In European Conference on Computer Vision, 546–555. Google ScholarDigital Library
16. Li, M., Langbein, F. C., and Martin, R. R. 2006. Constructing regularity feature trees for solid models. Geom. Modeling Processing, 267–286. Google ScholarDigital Library
17. Liu, Y., Collins, R., and Tsin, Y. 2004. A computational model for periodic pattern perception based on frieze and wallpaper groups. IEEE Trans. PAMI 26, 3, 354–371. Google ScholarDigital Library
18. Liu, S., Martin, R. R., Langbein, F. C., and Rosin, P. L. 2007. Segmenting periodic reliefs on triangle meshes. In Math. of Surfaces XII. Springer, 290–306. Google ScholarDigital Library
19. Mandelbrot, B. 1982. The Fractal Geometry of Nature. W. H. Freeman & Co.Google Scholar
20. Martinet, A., Soler, C., Holzschuch, N., and Sillion, F. X. 2006. Accurate detection of symmetries in 3d shapes. ACM Trans. Gr. 25, 2, 439–464. Google ScholarDigital Library
21. Mitra, N. J., Guibas, L. J., and Pauly, M. 2006. Partial and approximate symmetry detection for 3D geometry. ACM Trans. Gr. 25, 3, 560–568. Google ScholarDigital Library
22. Mitra, N. J., Guibas, L. J., and Pauly, M. 2007. Symmetrization. ACM Trans. Gr. 26, 3, #63. Google ScholarDigital Library
23. Müller, P., Zeng, G., Wonka, P., and Van Gool, L. 2007. Image-based procedural modeling of facades. ACM Trans. Gr. 26, 3, #85. Google ScholarDigital Library
24. Pauly, M., Mitra, N., Giesen, J., Gross, M., and Guibas, L. 2005. Example-based 3D scan completion. In Proc. Symp. Geometry Processing, 23–32. Google ScholarDigital Library
25. Podolak, J., Shilane, P., Golovinskiy, A., Rusinkiewicz, S., and Funkhouser, T. 2006. A planar-reflective symmetry transform for 3D shapes. ACM Trans. Gr. 25, 3, 549–559. Google ScholarDigital Library
26. Pottmann, H., Huang, Q.-X., Yang, Y.-L., and Hu, S.-M. 2006. Geometry and convergence analysis of algorithms for registration of 3D shapes. Int. J. Computer Vision 67, 3, 277–296. Google ScholarDigital Library
27. Rustamov, R. M. 2007. Augmented symmetry transforms. In Proc. Shape Modeling International. 13–20. Google ScholarDigital Library
28. Schaffalitzky, F., and Zisserman, A. 1999. Geometric grouping of repeated elements within images. In Shape, Contour and Grouping in Computer Vision, 165–181. Google ScholarDigital Library
29. Shikhare, D., Bhakar, S., and Mudur, S. P. 2001. Compression of large 3D engineering models using automatic discovery of repeating geometric features. In Vision, Modeling, and Visualization, 233–240. Google ScholarDigital Library
30. Simari, P., Kalogerakis, E., and Singh, K. 2006. Folding meshes: hierarchical mesh segmentation based on planar symmetry. In Proc. Symp. Geometry Processing. 111–119. Google ScholarDigital Library
31. Thompson, D. W. 1992. On Growth and Form. Dover.Google Scholar
32. Tuytelaars, T., Turina, A., and Gool, L. V. 2003. Non-combinatorial detection of regular repetitions under perspective skew. IEEE Trans. PAMI 25, 4, 418–432. Google ScholarDigital Library