Discovering structural regularity in 3D geometry

ABSTRACT

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.

REFERENCES

• 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.
• 2: Brown, J. C. 1991. Calculation of a constant Q spectral transform. J. Acoust. Soc. Am. 80, 425--434.
• 3: Antoni Buades , Bartomeu Coll , Jean-Michel Morel, Nonlocal Image and Movie Denoising, International Journal of Computer Vision, v.76 n.2, p.123-139, February 2008 [doi>10.1007/s11263-007-0052-1]
• 4: F. Cazals , M. Pouget, Estimating differential quantities using polynomial fitting of osculating jets, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 5: Dorin Comaniciu , Peter Meer, Mean Shift: A Robust Approach Toward Feature Space Analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.5, p.603-619, May 2002 [doi>10.1109/34.1000236]
• 6: Martin A. Fischler , Robert C. Bolles, Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography, Communications of the ACM, v.24 n.6, p.381-395, June 1981 [doi>10.1145/358669.358692]
• 7: Golovinskiy, A., Podolak, J., and Funkhouser, T. 2007. Symmetry-aware mesh processing. Tech. Rep. 782--07, Princeton Univ.
• 8: Grünbaum, B., and Shephard, G. C. 1987. Tilings and Patterns. W. H. Freeman.
• 9: Hall, B. C. 2003. Lie Groups, Lie algebras, and representations. An Elementary Introduction. Springer.
• 10: M. Hofer , B. Odehnal , H. Pottmann , T. Steiner , J. Wallner, 3D Shape Recognition and Reconstruction Based on Line Element Geometry, Proceedings of the Tenth IEEE International Conference on Computer Vision, p.1532-1538, October 17-20, 2005 [doi>10.1109/ICCV.2005.2]
• 11: Horn, B. K. P. 1987. Closed form solution of absolute orientation using unit quaternions. J. Opt. Soc. A 4, 629--642.
• 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.
• 13: Jacquin, A. 1992. Image coding based on a fractal theory of iterated contractive image transformations. IEEE Trans. Image Proc. 1, 1, 18--30.
• 14: Korah, T., and Rasmussen, C. 2007. 2D lattice extraction from structured environments. In Int. Conference on Image Processing, 61--64.
• 15: Thomas K. Leung , Jitendra Malik, Detecting, localizing and grouping repeated scene elements from an image, Proceedings of the 4th European Conference on Computer Vision-Volume I, p.546-555, April 15-18, 1996
• 16: Li, M., Langbein, F. C., and Martin, R. R. 2006. Constructing regularity feature trees for solid models. Geom. Modeling Processing, 267--286.
• 17: Yanxi Liu , Robert T. Collins , Yanghai Tsin, A Computational Model for Periodic Pattern Perception Based on Frieze and Wallpaper Groups, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.3, p.354-371, March 2004 [doi>10.1109/TPAMI.2004.1262332]
• 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.
• 19: Mandelbrot, B. 1982. The Fractal Geometry of Nature. W. H. Freeman & Co.
• 20: Aurélien Martinet , Cyril Soler , Nicolas Holzschuch , François X. Sillion, Accurate detection of symmetries in 3D shapes, ACM Transactions on Graphics (TOG), v.25 n.2, p.439-464, April 2006 [doi>10.1145/1138450.1138462]
• 21: Niloy J. Mitra , Leonidas J. Guibas , Mark Pauly, Partial and approximate symmetry detection for 3D geometry, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 22: Niloy J. Mitra , Leonidas J. Guibas , Mark Pauly, Symmetrization, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 23: Pascal Müller , Gang Zeng , Peter Wonka , Luc Van Gool, Image-based procedural modeling of facades, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 24: Mark Pauly , Niloy J. Mitra , Joachim Giesen , Markus Gross , Leonidas J. Guibas, Example-based 3D scan completion, Proceedings of the third Eurographics symposium on Geometry processing, July 04-06, 2005, Vienna, Austria
• 25: Joshua Podolak , Philip Shilane , Aleksey Golovinskiy , Szymon Rusinkiewicz , Thomas Funkhouser, A planar-reflective symmetry transform for 3D shapes, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 26: Helmut Pottmann , Qi-Xing Huang , Yong-Liang Yang , Shi-Min Hu, Geometry and Convergence Analysis of Algorithms for Registration of 3D Shapes, International Journal of Computer Vision, v.67 n.3, p.277-296, May 2006 [doi>10.1007/s11263-006-5167-2]
• 27: Raif M. Rustamov, Augmented Symmetry Transforms, Proceedings of the IEEE International Conference on Shape Modeling and Applications 2007, p.13-20, June 13-15, 2007 [doi>10.1109/SMI.2007.6]
• 28: Frederik Schaffalitzky , Andrew Zisserman, Geometric Grouping of Repeated Elements within Images, Shape, Contour and Grouping in Computer Vision, p.165-181, January 1999
• 29: Dinesh Shikhare , Sushil Bhakar , Sudhir P. Mudur, Compression of Large 3D Engineering Models using Automatic Discovery of Repeating Geometric Features, Proceedings of the Vision Modeling and Visualization Conference 2001, p.233-240, November 21-23, 2001
• 30: Patricio Simari , Evangelos Kalogerakis , Karan Singh, Folding meshes: hierarchical mesh segmentation based on planar symmetry, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 31: Thompson, D. W. 1992. On Growth and Form. Dover.
• 32: Tinne Tuytelaars , Andreas Turina , Luc Van Gool, Noncombinatorial Detection of Regular Repetitions under Perspective Skew, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.4, p.418-432, April 2003 [doi>10.1109/TPAMI.2003.1190569]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Keywords:
regular structure, repetitive pattern, shape analysis, similarity transformation, transformation group