Towards Visual Perception of Periodic Tilings: A Computational Model

Year: 1999 Authors: Kristyann Manske; Amir Assadi; Hamid Eghbalnia; Stephen Palmer

Core claim

Detecting translation and reflection symmetries is sufficient to characterize repetitive planar patterns, and a geometric-statistical algorithm can estimate the fundamental domain for such tilings.

Topics

translation symmetry, periodic tilings, visual perception, computer vision, psychophysics

Domains

geometry, symmetry theory, tiling theory, statistics, linear algebra, pattern design, visual arts, texture analysis

Methods

computational modeling, geometric analysis, statistical considerations, algorithm design, psychophysical comparison

Media

planar surfaces, textured images, robot camera images, spike trains, visual stimuli

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

BRIDGES Mathematical Connections in Art, Music, and Science

Towards Visual Perception of Periodic Tilings: A Computational Model

Kristyann Manske Center for the Mathematical Sciences University of Wisconsin at Madison, WI 53715

Amir Assadi and Hamid Eghbalnia Department of Mathematics University of Wisconsin at Madison, WI 53715

Stephen Palmer Department of Psychology and Center of Cognitive Studies University of California at Berkeley, CA 94720

Abstract

Symmetry is important in the development and performance of the visual system. Most of the current research findings on perception and computational modeling of symmetry focus on the biological significance of bilateral symmetry in the visual system of primates and psychophysics of reflection symmetry in human vision. There seems to be little previous work done on modeling detection of translation symmetry in the human visual system. In this paper, we study the problem of detection and characterization of translation symmetry in plane surfaces. We also explore their generalization to the case of a planar surface situated in the 3-space with a slant, tilt, or both. Besides contribution to computational modeling of human visual perception of symmetry, this research provides algorithms for characterization of texture and geometric properties of planar surfaces in computer vision.

On the theoretical side, we discuss the reduction of a complete solution to perception of arbitrary planar symmetries to the special cases of characterization of translations and reflections. On the computational side, we provide an algorithm based on geometric and statistical considerations to detect and determine the fundamental domain for translation symmetries in planar surfaces parallel to the viewer’s eye (or the robot camera’s image plane). We have included a brief review and critique of results from mathematics of tiling, psychophysics, and neurobiology of the visual systems pertaining to detection of bilateral symmetry. Finally, we discuss the limitations and successes of our algorithms, and the issues of effectiveness and performance of our computation methods.

Introduction

Symmetry is a manifestation of structural harmony of objects and of transformations leaving invariant their geometric structure. Symmetry has played a ubiquitous role in our civilization throughout all ages. In all intellectual pursuits, symmetry lies at the very foundation of intuitive geometric reasoning [1]¹. Humankind has been fascinated by the inherent beauty of symmetry in Nature, and we have explored and searched for understanding of its implications in our cultures [2]. This preoccupation with symmetry has led to discovery of rich mathematical theories to explain and apply in a vast number of subjects ranging

¹ Here, we would like to use the term symmetry in reference to all kinds of transformations that leave invariant some form of geometry, together with its related cognitive concepts such as harmony. Therefore, similarity in Euclidean plane geometry is a form of symmetry (in the so-called conformal geometry, where angles are preserved) although it is not necessarily a rigid motion. The term quasi-symmetry may be used for perceived regularity of structure that is compelling in its organization, but fails to be a strict symmetry in the mathematical sense above.

Kristyann Manske, Amir Assadi, Hamid Eghbalnia, and Stephen Palmer

from anthropology [2] and the arts, to engineering and the sciences [1, 3-5]. In applications, symmetry plays an equally key role for modeling perception of the outside 3-dimensional world [6-8].

The remaining parts of the paper are listed below. In the next section, besides a brief discussion of background from cognitive science, we outline how the present computational model generalizes to a computational theory for detection of translation regularity of geometric structure of natural (or synthetic) surfaces. In Section Two, we justify in outline why detection of only two simple kinds of symmetries, translation and reflection, is sufficient for detection of repetitive patterns on surfaces. In Section Three, we present our computational model with a discussion of the algorithms and their implementation. Section Four contains a brief analysis of the weaknesses of the software, and proposes a method for evaluation of performance of computational models based on statistical accuracy of the predictions as well as psychophysical experiments designed to compare human versus machine performance. Finally, Section Five contains a brief description of Principal Component Analysis, a promising technique for improving our computational model.

Section One: Background and Motivation

Our research has a long-term objective: to investigate the cognitive processes that underlie our perception of geometric forms. We believe that the time is ripe to address such issues in the realm of cognitive neuroscience. Computational models serve to investigate and support the cognitive theories. In addition, computational models reveal the potential approaches to cognitive and/or biological models. One could generally agree that computational simulations prevent possible pitfalls in realistic models, and play an important role in providing hints to avoid resource-intensive approaches. It is likely that the increasingly rapid pace of advances in our understanding of the biology of the brain and advances in computation power will open new ways for investigation of information processing in the brain. Thus, we are optimistic that in foreseeable future, we will have the scientific tools to understand neuronal substrates of low-level computations of visual, tactile, motor and auditory processes that contribute to our perception of symmetry and regularity in structure.

This paper is a first computational attempt at modeling detection of repetitive patterns in visual perception in the presence of noise and natural imperfections of visual stimuli. Being as small a step as it may be, we propose a possible approach for visual perception of geometric form of surfaces endowed with symmetric patterns in their texture. The key biological observation is the dynamic nature of vision: visual perception of the physical world depends on saccades, the tiny, almost instantaneous jitters of the eyeballs [9] (e.g. see pp. 78-80). Without such seemingly random motions of the eyes, the photoreceptor cells of the retina get chemically saturated from the steady invasion of photons, and the image on the retina ceases to exist! All neurons in the visual cortex have receptive fields [9] defined, roughly speaking, as the cone-shaped region of the space measured in terms of the visual angle. The concept of the receptive field and its biological properties leads us to hypothesize that: there is a biologically realistic hybrid computational model of intermediate-level vision in which the process of neuronal detection of visual symmetry in the presence of repetitive patterns involves an adaptive series of comparison of patterns of spike trains. This is due to visual stimuli that are brought about by a sequence of saccades.

We refer to this statement as the Adaptive Saccades Hypothesis for detection of symmetry. The long-term goal of the present research includes formulation and verification of models that incorporate hypotheses such as the Adaptive Saccades Hypothesis above. Therefore, our first attempt focuses on modeling adaptive processes that simulate saccades and comparison of the resulting neural activation, in

2 Spike train refers to the pattern of neuronal firing, or action potentials, recorded by electrophysiological measurement from outside or inside of a neuron.

Towards Visual Perception of Periodic Tilings: A Computational Model 213

parlance of neural networks and learning theory [10]. In this paper, we consider a simplified version of the above-mentioned theory: a computational model is presented that detects the fundamental domain for translation symmetry of patterns on a flat surface parallel to the observer’s plane of view (or the robot’s camera screen). This model is robust with respect to noise, partial occlusion and some irregularity in the translational symmetry. In a forthcoming paper, we present the generalization of this model to incorporate saccades and visual learning [11].

Section Two: Translation Symmetry and Geometric Theories for Perception of Texture

One approach to learning how the human visual system works is to study how the brain detects symmetry. Here is a brief description of some different types of symmetry. It is followed by a few brief remarks on previous work studying human perception of symmetry, and a description of how this paper and forthcoming papers naturally extend the existing work.

From a purely mathematical viewpoint, it is well known that the group of symmetries of tessellations of the Euclidean plane is generated by composition of two types of transformations: reflections (in suitable axis) and translations. For example, Figure 1 shows an image that has reflection symmetry about the vertical and horizontal axes.

A generalization of tessellation is tiling of the plane. A tiling need not have any symmetry at all, a jigsaw puzzle is an example of this. However, of interest are periodic tilings, which can be recreated by tiling a small subset of the image. An example of a periodic tiling is shown in Figure 2. More formally, a periodic tiling contains a fundamental domain, which is a parallelogram ${}^3$ $\mathbf{p}$ that satisfies the properties below:

1. The plane can be covered with a family $\mathbf{P}$ of parallelograms that are translates of $\mathbf{p}$ , without any two-dimensional overlaps or gaps.
2. No reflections or rotations of $\mathbf{p}$ are allowed.
3. $\mathbf{p}$ is the parallelogram with minimum area that satisfies these properties.

See [12] for a more complete discussion.

Figure 2

One of the key tasks of the software described later in this paper is to find the fundamental domain of an input image, if there is any.

It is worth mentioning that we do not have still any satisfactory biological and impeccable psychophysical evidence that provide a convincing theory of perception of symmetry of patterns, even in the simplest circumstances. One example is a flat plane parallel to the observer’s view plane (perpendicular to the line passing through the cyclopean eye ${}^3$ ). Nonetheless, it is convenient, and not so

214 Kristyann Manske, Amir Assadi, Hamid Eghbalnia, and Stephen Palmer

unreasonable to start with the assumption that any computational theory of perception of symmetry would most likely use the special cases of translation and reflection of planar periodic tilings as one of its building blocks; see e.g. [13]. As for reflection symmetries, there is a great deal of research that is partially outlined in [14] and elsewhere (e.g.[15] [16-18]). In fact, almost all articles in that volume are devoted to bilateral and reflection symmetry, (e.g. [19, 20]), with a few exceptions dealing with circular and rotation symmetries [21]. Translation symmetry seems, for the most part, not adequately covered in the literature (see [22-24]). As for connectionist models, backpropagation models for detection of reflection symmetry are provided in [10, 22]. Finally, Dakin and Watt have used spatial filters for detection of bilateral symmetry [20]. Thus, for the remaining part of this paper, we concentrate on translation symmetry.

The research reported in this article explores a computational theory for visual discovery of regular patterns on almost smooth flat surfaces. If we momentarily assume a smooth surface, the simplest case of this problem is detecting translation symmetry (or tiling) on a flat surface parallel to the observer’s plane of view. To simplify the problem further, one reduces the texture to a grayscale intensity pattern (in other words, removes color). Nonetheless, the complications due to noise, imperfect images, and slight irregularities in natural and synthetic textured surfaces cannot be ignored by a theory that aims to generalize perception of natural surfaces in the environment. While the case of flat surfaces is quite special, it plays a key role in the development of the theory for general surfaces. To this end, we consider the problem of estimating the geometric properties of a textured surface whose underlying mathematical surface in 3-D is piecewise smooth. At almost all points, one defines a “textured tangent space” to the surface [25], which is a plane (a flat surface) situated in 3-D in a position that is not necessarily parallel to the observer’s plane of view. In a related work, we address the problem of estimating slant and tilt (in the sense of computer vision) of textured planes with translation symmetry [25]. How does one handle the case of non-smooth surfaces? In [26], we have proposed a possible approach via the concept of Gestalt of surfaces, that reduces the problem of estimation of geometric properties of general surfaces to the case of piecewise smooth surfaces endowed with texture. Putting together these results, one has the fundamental geometric and computational tools for detection of symmetric patterns on surfaces in the case of translation (i.e. repetitive patterns) for a fairly broad class of natural surfaces. Our theory handles the imperfections of the images quite well for the most part, while there are still a number of possibilities for almost regularity that are not detected by the present software. Several typical examples are treated below.

Besides applications in science and technology, we hope that the long-term objectives of this research draw the attention of a more general audience to the fundamental role of quantitative and qualitative geometric methods that accompany the intuitive reasoning in many aspects of human creativity and discovery.

Section Three: A Computational Model

Periodic Tiling Detector (PTD) is a Matlab${}^6$ program that detects the fundamental domain of an input image. The basic idea behind PTD is as follows: a combination of translation and scaling symmetries are used to compare adjacent squares of increasing size in the image. A global comparison algorithm that incorporates the best fit determines the optimal size and a pair of squares that are most similar. This determines the horizontal periodicity in the image. This is repeated on the transpose of the image to find the vertical periodicity. (Please see Appendix 1 for a simplified version of the psuedocode.)

Here we describe the types of noise PTD can robustly handle in an input image. Figure 3 is an input image artificially generated by [27] that has sections missing, noise inserted, and differing levels of

${}^6$ Matlab© is the software package for scientific computation available from MathWorks Inc.

Towards Visual Perception of Periodic Tilings: A Computational Model 215

blur. Figure 4 is PTD’s reproduction of the tiling. Despite all the distractions in the input image, PTD was able to reconstruct the original image.

Figure 3 Noisy Input Image

Figure 4 PTD Reproduction

Figure 5 is a photograph of a tiling. The image is slightly skewed, which is easily seen when looking at the lower left corner. Additionally, the light colored sideways triangles are quite different from each other. Figure 6 shows PTD’s replication of the image. While the input image is slightly tilted, the replication is not, as it can be seen by comparing the lower left corners of Figures 5 and 6.

Figure 5 Photograph of a Tiling

Figure 6 PTD Reproduction

Here are several situations that are not handled well by PTD, as well as a brief description of a possible remedy. Some points that will be enhanced in the forthcoming versions of the software are as follows:

Detecting Non-Periodicity. Thus far the program is not equipped to alert the user when an input image probably does not have periodicity. This could be remedied by doing a study of the error rate of periodic and non-periodic images (see the following section on an evaluation metric).

Noise in Upper Left of Image. Currently PTD uses the upper left corner squares to get correlation measures. If the upper left corner is noisier than the rest of the image, the correlation results could be meaningless. This could possibly be resolved by starting PTD from several points in the input image, not just the upper left.

Non-Rectangular Lattices. Because PTD uses adjacent squares for correlation, it does not detect periodicity in images that cannot be tiled with rectangles’ parallel to the x-axis (see Figure 7). This type of problem may be solved with Principal Component Analysis (briefly described later in the paper).

7 More technically, the parallelograms which make up the tiling’s lattice are not necessarily rectangular.

216 Kristyann Manske, Amir Assadi, Hamid Eghbalnia, and Stephen Palmer

Figure 7 This image clearly has periodicity; however, there is no rectangular subset of the image that could recreate the entire image by tiling.

PTD Does Not Model Human Vision Process. The results of PTD are comparable to human perception; it is difficult to tell the difference between Figures 5 and 6. However, PTD’s current algorithm is not likely to closely model actual human perception. A future version that models saccades, for instance, is biologically closer to a more accurate model.

Section Four: A Metric for Evaluation of Computational Models

A metric for evaluating the output of PTD is necessary in order to expand the algorithm to indicate when an input image is not likely to contain a periodic tiling (see Section Five). For the experiments described in this paper, the metric used was:

mean(standard_deviation_of_columns(InputImage – PTD_Reproduction)).

A method for evaluating the robustness of PTD is to add an increasing amount of noise to an image to determine when PTD is no longer able to detect a tiling. Figure 8 is a polka-dot pattern with Gaussian noise added⁸, and Figure 9 shows the PTD reproduction at 23 iterations. After 23 iterations of adding noise, the error metric rose above 90 and PTD’s performance began to decline. At 35-40 iterations of adding noise, the input image became too noisy for a human observer to determine the regularity.

There is a statistically well-defined threshold of noise at which the computational model fails to reliably detect the regularity of a tiling pattern in an image. We propose to follow up our research with psychophysical experiments to evaluate the above-mentioned computation threshold versus a similar human threshold for the same set of images.

⁸ Each iteration applied zero mean Gaussian noise with 0.01 variance to the input image.

Towards Visual Perception of Periodic Tilings: A Computational Model

Figure 8 Input image containing Gaussian noise.

Figure 9 PTD Reproduction

Figure 10 Avg. Standard Deviation Metric (y-axis) vs. Images Containing an Increasing Amount of Noise (x-axis)

Section Five: Work in Progress and Future Research

An alternative and complimentary method for discovering the fundamental domain of symmetries can use the methods of Principal Component Analysis. In the principal component transformation approach one is initially given a $n\times p$ matrix $X$ of discrete observations $-n$ observations of $p$ variables. Let $X_{\ast i}$ and $X_{j\ast }$ be the $i^{\text{th}}$ row and $j^{\text{th}}$ column vector respectively. In general, the $p$ vectors are not independent and we seek a subset of $s$ vectors that contain the same information as $X$ – that is an $n\times s$ set of so-called feature vectors. If the relationship between the observed vectors and feature vectors is linear (with possible noise) then PCA can be used.

Briefly, let $X{X}^T=UA{U}^T$ be the singular value decomposition of $X{X}^T$ where $A$ is the diagonal matrix of eigenvalues $a_i$ . The principal component transformation is given by $R=XU$ . Columns of $U$

218 Kristyann Manske, Amir Assadi, Hamid Eghbalnia, and Stephen Palmer

represent the principal directions and the direction corresponding to the maximum eigenvalue $a_i$ has maximal variance. Each $a_j$ represents the variance along the $j^{\text{th}}$ principal direction represented by the $j^{\text{th}}$ column of U. Properly chosen samples of the image represent vectors of the sample matrix X. Since X has symmetries, the actual dimension of the feature space is less than the sample space X. If assumption about noise and the relationship of the feature and sample space are met, the fundamental domain can be recovered as principal components of the sample. We remark that special cases of computational modeling of symmetry perception are studied by other authors, e.g. [10, 28] and their relevant references.

Acknowledgement

The authors thank John Carew for careful reading the manuscript and his helpful comments. We also thank the National Science Foundation for partial support under the grants EHR-DUE-CCD and DMS-KDI-LIS, and the offices of the Provost and Vice Chancellor for Administration of the University of Wisconsin-Madison for support of the Project Symmetry.

Dedication

This paper is dedicated to the memory of Nargess Nateghi.

Towards Visual Perception of Periodic Tilings: A Computational Model 219

Appendix 1: Psuedocode for PTD

/* Image I of width d[2] and height d[1] is presented */
d[2] = width_of_image
d[1] = height_of_image
z = max(d[2],d[1])
w = initialize_to_max_float(z)  // w is an array of size = max(d[2],d[1])
num_select = 25;
w2 = initialize_to_max_float(num_select)
l = initialize_to_max_float(2)  // l is an array of size = 2
sample_size = 2
for j = 1 to 2 do
I = transpose(I)  // First loop finds best vertical periodicity,
// second loop finds best horizontal
// periodicity.
// First for loop: Incrementing the size of the square, record how much alike the
// upper left two adjacent squares are as the size increases.
for k = sample_size to d[j]/2 do
square = I(1:sample_size, 1:sample_size)
// I(1:s,1:s) is a square of size s in upper
// left corner.
square2 = I(1:sample_size, sample_size+1:2*sample_size)
// The adjacent square
w[k] = distance_measure(square, square2)
// measure difference in some metric
end
[Index, w] = sort(w, "Ascending")  // Sort results in ascending order.
// Index[i] is an array element that stores the square size that is associated
// with the measure in w[i] after sorting. (The square size is the same
// thing as sample_size from each increment.)
// Second for loop: Find out which of the top-scoring squares best describes
// the periodicity of the image.
for k = 1 to num_select do
strip = I(:, 1:Index[k])  // A strip that has the same width as the i^th
// best scoring square.
O = tile(strip,I)  // Tile with strip to create an image of size I.
w2[k] = distance_measure(O,I)
end
w2 = sort(w2, "Ascending")  // Sort results in ascending order.
l[j] = w2[1];  // Select the smallest value.
w = initialize_to_max_float;  // Reinitialize.
end
return(l)  // l contains the size of the rectangle
 
220 Kristyann Manske, Amir Assadi, Hamid Eghbalnia, and Stephen Palmer
 
## References
 
1. Shubnikov, A.V.a.K., V.A., *Symmetry in Science and Art*. 1972: Plenum Press.
2. Washburn, D.K., and Crowe, D. W., *Symmetries of Culture*. 1988, Seattle, WA: University of Washington Press.
3. Weyl, H., *Symmetry*. 1952, Princeton, NJ: Princeton University Press.
4. Hargittai, I.a.H., M., *Symmetry through the Eyes of Chemist*. Second Edition ed. 1995: Plenum Publishing Corporation.
5. Heilbronner, E.a.D., *Jack, Reflections on Symmetry, in Chemistry ... and Elsewhere*. 1993: Verlag Helvetica Chimica Acta, Basel.
6. Kanade, T.a.K., J. R., *Mapping image properties into shape constraints: Skewed symmetry, affine-transformable patterns, and the shape-from-texture paradigm.*, in *Human and Machine Vision*, J. Beck, Hope, B., and Rosenfeld, A., *Editor*. 1983, Academic Press: New York. p. 237-257.
7. Vetter, T., and Poggio, T., *Symmetric 3D objects are an easy case for 2D object recognition*, in *Human Symmetry Perception*, C.W. Tyler, Editor. 1996, VSP BV: Utrecht, the Netherlands. p. 349-359.
8. Loffeld, O., *Centre national de la recherche scientifique (France)*, and *Society of Photo-optical Instrumentation Engineers.*, *Vision systems--sensors, sensor systems, and components : 10-12 June 1996, Besancon, France*. Proceedings of SPIE--the International Society for Optical Engineering ; v. 2784. 1996, Bellingham, Wash., USA: SPIE--the International Society for Optical Engineering. v, 154.
9. Hubel, D., *Eye, Brain, and Vision*. Scientific American Library Series. Vol. #22. 1995: W.H. Freeman and Company.
10. Latimer, C., Joung, W., and Stevens, C., *Modelling symmetry detection with back-propagation networks*, in *Human Symmetry Perception*, C.W. Tyler, Editor. 1996, VSP BV: Utrecht, the Netherlands. p. 209-225.
11. Eghbalnia, H., Assadi, A., and Manske, K., *Saccades and Symmetry*. Preprint, Center for the Mathematical Sciences, UW-Madison, 1999. (Submitted for publication.)
12. Gruenbaum, B., Shephard, G. C., *Tilings and Patterns: an Introduction*. 1996: W. H. Freeman.
13. Royer, F.L., *Detection of symmetry*. J. Exp. Psychol: Human percept. Perform., 1981. 7: p. 1186-1210.
14. Tyler, C.W., ed. *Human Symmetry Perception and its Computational Analysis*. . 1996, VSP BV: Utrecht, the Netherlands. 393.
15. Gerbino, W.a.Z., L., *Visual orientation and symmetry detection under affine transformations*. Bull. Psychonom. Soc., 1991. 29: p. 480.
16. Wagemans, *Detection of visual symmetries*, in *Human Symmetry Perception*, C.W. Tyler, Editor. 1996, VSP BV: Utrecht, the Netherlands.
17. Wagemans, J., Van Gool, L. and d'Ydewalle, G., *Orientational effects and component processes in symmetry detection*. Q. J. Exp. Psychol., 1992. 44A: p. 475-508.
18. Wagemans, J., Van Gool, L., Swinnen, V., and Van Horebeek, J., *Higher-order structure in regularity detection*. Vision Res., 1993. 33: p. 1067-1088.
19. Marola, G., *On the detection of the axes of symmetry of symmetric and almost symmetric planar images*. IEEE Trans. Pattern Anal. Machine Intell., 1989. PAMI-11: p. 104-108.
20. Dakin, S.C.a.W., R. J., *Detection of bilateral symmetry using spatial filters*, in *Human Symmetry Perception*, C.W. Tyler, Editor. 1996, VSP BV: Utrecht, the Netherlands. p. 187-207.
21. Palmer, S.E.a.H., K., *Orientation and symmetry: Effects of multiple, rotational, and near symmetries*. J. Expo. Psychol: Human Percept. Perform., 1978. 16: p. 150-163.
22. Baylis, G.C.a.D., J., *Parallel computation of symmetry but not repetition within single visual shapes*. Visual Cognit., 1994. 1: p. 377-400.
23. Bruce, V.G.a.M., M. J., *Violations of symmetry and repetition in visual patterns*. Perception, 1975. 4: p. 239-249.
24. Corballis, M.C.a.R., C.E., *On the perception of symmetrical and repeated patterns*. Percept. Psychophys., 1974. 16: p. 136-142.
25. Assadi, A., Palmer, S., and Eghbalnia, H., ed. *Learning Gestalt Of Surfaces In Natural Scenes*. Proceedings of IEEE Int. Conf. Neural Networks in Signal Processing, ed. J.a.H. Larsen, H.Y. 1999.
26. Assadi, A., Lu, Chunmei, Eghbalni, Hamid, *Learning the Geometry of Textured Surfaces*. Preprint, 1999.
27. Amenta, N., Phillips, M., Weeks, J., *Java Kali*, . 1996, University of Minnesota (The Geometry Center).
28. Kurbat, M.A., *A network model for generating differential symmetry axes of shapes via receptive fields*, in *Human Symmetry Perception*, C.V. Tyler, Editor. 1996, VSP BV: Utrecht, the Netherlands. p. 227-236.