| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Computational Model for Periodic Pattern Perception Based on Frieze and Wallpaper Groups
March 2004 (vol. 26 no. 3)
pp. 354-371
Abstract—We present a computational model for periodic pattern perception based on the mathematical theory of crystallographic groups. In each N-dimensional Euclidean space, a finite number of symmetry groups can characterize the structures of an infinite variety of periodic patterns. In 2D space, there are seven frieze groups describing monochrome patterns that repeat along one direction and 17 wallpaper groups for patterns that repeat along two linearly independent directions to tile the plane. We develop a set of computer algorithms that "understand” a given periodic pattern by automatically finding its underlying lattice, identifying its symmetry group, and extracting its representative motifs. We also extend this computational model for near-periodic patterns using geometric AIC. Applications of such a computational model include pattern indexing, texture synthesis, image compression, and gait analysis.
[1] L. Bieberbach, Über die Bewegungsgruppen der n-Dimensional en Euklidischen Räume Mit Einem Endlichen Fundamental Bereich Göttinger Nachrichten, pp. 75-84, 1910.
[2] R.W. Conners and C.A. Harlow, Toward a Structural Textural Analyzer Based on Statistical Methods Proc. Int'l Conf. Color in Graphics and Image Processing, vol. 12, no. 3, pp. 224-256, Mar. 1980.
[3] R. Cutler and L.S. Davis, Robust Real-Time Periodic Motion Detection, Analysis, and Applications IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 8, Aug. 2000.
[4] A.A. Efros and W.T. Freeman, Image Quilting for Texture Synthesis and Transfer Proc. SIGGRAPH, pp. 35-42, 2001.
[5] R. Enrich and J.P. Foith, A View of Texture Topology and Texture Description Proc. Conf. Computer Graphics Image Processing, vol. 8, pp. 174-202, 1978.
[6] J.A. Gallian, Contemporary Abstract Algebra. Lexington, Mass.: D.C. Heath and Company, 1986.
[7] A.D. Gross and T.E. Boult, Analyzing Skewed Symmetries Int'l J. Computer Vision, vol. 13, no. 1, pp. 91-111, Sept. 1994.
[8] R. Gross and J. Shi, The CMU Motion of Body (MoBo) Database Technical Report CMU-RI-TR-01-18, Robotics Inst., Carnegie Mellon Univ., 2001.
[9] B. Grünbaum and G.C. Shephard, Tilings and Patterns. New York: W.H. Freeman and Company, 1987.
[10] Int'l Tables for X-Ray Crystallography, vol. 1, Symmetry Groups, N.F.M. Henry and K. Lonsdale, eds., The Kynoch Press, England, The Int'l Union of Crystallography, 1969.
[11] O. Jones, The Grammar of Ornament. New York: Van Nostrand Reinhold, 1972.
[12] D. Joyce, Wallpaper Groups (Plane Symmetry Groups),aleph0. clarku.edu/~djoyce/wallpaperwall1.html , 2003.
[13] J. Kahn and D. Foster, Horizontal-Vertical Structure in the Visual Comparison of Rigidly Transformed Patterns J. Experimental Psychology: Human Perception and Performance, vol. 12, pp. 422-433, 1986.
[14] T. Kanade, Recovery of the 3-Dimensional Shape of an Object from a Single View Artificial Intelligence, vol. 17, pp. 75-116, 1981.
[15] T. Kanade and J.R. Kender, Mapping Image Properties into Shape Constraints: Skewed Symmetry, Affine-Transformable Patterns, and the Shape-from-Texture Paradigm Readings in Computer Vision: Issues, Problems, Principles, and Paradigms, M.A. Fischler and O. Firschein, eds. pp. 257-267, Kaufmann, 1987.
[16] K. Kanatani, Statistical Optimization for Geometric Computation: Theory and Practice (Machine Intelligence and Pattern Recognition), vol. 18, North-Holland, 1996.
[17] K. Kanatani, “Comments on“Symmetry as a Continuous Feature”,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 3, pp. 246-247, Mar. 1997.
[18] M. Kazhdan, B. Chazelle, D. Dobkin, A. Finkelstein, and T. Funkhouser, A Reflective Symmetry Descriptor Proc. Seventh European Conf. Computer Vision, pp. 642-656, May 2002.
[19] T. Leung and J. Malik, Detecting, Localizing and Grouping Repeated Scene Elements Proc. European Conf. Computer Vision, vol. 1, pp. 546-555, 1996.
[20] M. Leyton, Symmetry, Causality, Mind. Cambridge, Mass.: MIT Press, 1992.
[21] L.G.C. Hamey and T. Kanade, Computer Analysis of Regular Repetitive Textures Proc. Image Understanding Workshop, pp. 1076-1088, 1989.
[22] H.-C. Lin, L.-L. Wang, and S.-N. Yang, Extracting Periodicity of a Regular Texture Based on Autocorrelation Functions Pattern Recognition Letters, vol. 18, pp. 433-443, 1997.
[23] J. Liu, J.L. Mundy, D.A. Forsyth, A. Zisserman, and C.A. Rothwell, “Efficient Recognition of Rotationally Symmetric Surface and Straight Homogeneous Generalized Cylinders,” Proc. Conf. Computer Vision and Pattern Recognition, pp. 123-129, June 1993.
[24] Y. Liu and R.T. Collins, A Computational Model for Repeated Pattern Perception Using Frieze and Wallpaper Groups Proc. Computer Vision and Pattern Recognition Conf., pp. 537-544, http://www.ri.cmu.edu/pubspub_3302.html, June 2000.
[25] Y. Liu and R.T. Collins, Skewed Symmetry Groups Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 872-879, , Dec. 2001.
[26] Y. Liu and R.T. Collins, Frieze and Wallpaper Symmetry Groups Classification under Affine and Perspective Distortion Technical Report CMU-RI-TR-98-37, The Robotics Inst., Carnegie Mellon Univ., Pittsburgh, Penn., 1998.
[27] Y. Liu, R.T. Collins, and Y. Tsin, Gait Sequence Analysis Using Frieze Patterns Proc. Seventh European Conf. Computer Vision, 2002.
[28] Y. Liu and W.C. Lin, Deformable Texture: The Irregular-Regular-Irregular Cycle Proc. Third Int'l Workshop Texture Analysis and Synthesis (Texture 2003), Oct. 2003.
[29] Y. Liu and R. Popplestone, A Group Theoretical Formalization of Surface Contact Int'l J. Robotics Research, vol. 13, no. 2, pp. 148-161, Apr. 1994.
[30] Y. Liu, Y. Tsin, and W.C. Lin, The Promise and Perils of Near-Regular Texture Int'l J. Computer Vision, accepted for publication, 2003.
[31] G. Loy and A. Zelinsky, A Fast Radial Symmetry Transform for Detecting Points of Interest Proc. European Conf. Computer Vision, p. 358, 2002.
[32] S.Y. Lu and K.S. Fu, A Syntactic Approach to Texture Analysis Computer Graphics Image Processing, vol. 7, pp. 303-330, Nov. 1978.
[33] G. Marola, "On the Detection of the Axes of Symmetry of Symmetric and Almost Symmetric Planar Images," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, pp. 104-108, 1989.
[34] W. Miller Jr., Symmetry Groups and Their Applications. New York: Academic Press, 1972.
[35] S.C. Pei and L.G. Liou, Automatic Symmetry Determination and Normalization for Rotationally Symmetric 2D Shapes and 3D Solid Objects Pattern Recognition, vol. 27, pp. 1193-1208, 1994.
[36] A.R. Rao and G.L. Lohse, Identifying High Level Features of Texture Perception CVGIP: Image Processing, vol. 55, pp. 218-233, 1993.
[37] J. Russ, The Image Processing Handbook, second ed., CRC Press, 1995.
[38] F. Schaffalitzky and A. Zisserman, Geometric Grouping of Repeated Elements within Images Shape, Contour, and Grouping in Computer Vision, D.A. Forsyth, V. Di Gesu, J.L. Mundy, and R. Cipolla, eds., Springer-Verlag, 1999.
[39] D. Schattschneider, The Plane Symmetry Groups: Their Recognition and Notation Am. Math. Monthly, vol. 85, pp. 439-450, 1978.
[40] D. Schattschneider, personal communications, 1999.
[41] R.L.E. Schwarzenberger, The 17 Plane Symmetry Groups Math. Gazette, vol. 58, pp. 123-131, 1974.
[42] K. Selkainaho, J. Parkkinen, and E. Oja, Comparison of x2 and k Statistics in Finding Signal and Picture Periodicity Proc. Int'l Conf. Pattern Recognition, pp. 1221-1224, 1988.
[43] A.V. Shubnikov and V.A. Koptsik, Symmetry in Science and Art. D. Harkar, ed., New York: Plenum Press, 1974.
[44] V.V. Starovoitov, S.Y. Jeong, and R.H. Park, Texture Periodicity Detection: Features, Properties, and Comparisons IEEE Trans. Systems, Man, and Cybernetics, Part A, vol. 28, no. 6, pp. 839-848, 1998.
[45] P. Stevens, Handbook of Regular Patterns. Cambridge, Mass.: MIT Press, 1987.
[46] C.M. Sun, Fast Recovery of Rotational Symmetry Parameters Using Gradient Orientation Optical Eng., vol. 36, no. 4, pp. 1073-1077, Apr. 1997.
[47] T. Tuytelaars, A. Turina, and L. Van Gool, Noncombinatorial Detection of Regular Repetitions under Perspective Skew IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, pp. 418-432, 2003.
[48] L. Van Gool, T. Moons, and M. Proesmans, “Mirror and Point Symmetry under Perspective Skewing,” Proc. Conf. Computer Vision and Pattern Recognition, pp. 285-292, 1996.
[49] D.K. Washburn, Perceptual Anthropology: The Cultural Salience of Symmetry Am. Anthropologist, vol. 101, no. 3, pp. 547-562, 1999.
[50] D.K. Washburn and D.W. Crowe, Symmetries of Culture: Theory and Practice of Plane Pattern Analysis. Univ. of Washington Press, 1991.
[51] J. Weeks, Programs that Can Automatically Generate 2D Planar Crystallographic Patterns, Kali,http://www.ri.cmu.edu/pubs/pub_3815.htmlhttp:/ /www.geom.umn.edu/apps/Kali, 1995.
[52] R.K.K. Yip, W.C.Y. Lam, P.K.S. Tam, and D.N.K. Leung, A Hough Transform Technique for the Detection of Rotational Symmetry Pattern Recognition Letters, vol. 15, no. 9, pp. 919-928, Sept. 1994.
[53] H. Zabrodsky, S. Peleg, and D. Avnir, "Symmetry as a Continuous Feature," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, pp. 1,154-1,166, 1995.
[54] S.W. Zucker and D. Terzopoulos, Finding Structure in Cooccurrence Matrices for Texture Analysis Proc. Int'l Conf. Color in Graphics and Image Processing, vol. 12, no. 3, pp. 286-308, Mar. 1980.
Index Terms:
Periodic pattern, frieze group, wallpaper group, symmetry group, lattice, tiles, motifs, gait analysis.
Citation:
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, vol. 26, no. 3, pp. 354-371, Mar. 2004, doi:10.1109/TPAMI.2004.1262332
