Project Description
Background:The research I'm working with is based on the symmetries of periodic patterns in textures. Classification of these symmetries is done using crystallographic groups -- a finite set of symmetry groups that completely describes the possible symmetries of any periodic pattern in n dimensions[1]. In one dimension, these are the Frieze groups, in two, the wallpaper groups.
Identification of the wallpaper group of a regular texture is done by first identifying the vectors that preserve the pattern upon translation, and hence creating an overlaying lattice stucture. A 'median' tile, which can be thought of as the smallest representative unit of the texture is then extracted, by cutting parts of the pattern along the lattice, comparing these parts with the corresponding translated areas of the pattern, and obtaining a median value for each pixel of the tile.
The symmetry detection is then done by rotating the image by 60, 90, 120 and 180 degrees, and reflecting (or glide-reflecting) it along the translation vectors and their diagonals. A good correlation between a transformed pattern and the median tile indicates the existence of a symmetry about that transformation.
The table below shows the wallpaper groups and their symmetry combinations. (Source:[1])
The first four columns indicate rotation angles. T1 and T2 indicate reflections about the respective lattice lines, and D1 and D2 stand for reflection about the lines diagonal to the lattice vectors. 'Y' denotes the existence of a symmetry about that particular rotation or reflection, and 'Gld' denotes the existence of a symmetry upon glide reflection.
Group\Sym |
180o |
120o |
90o |
60o |
T1 |
T2 |
D1 |
D2 |
P1 |
||||||||
P2 |
Y |
|||||||
PM |
Y | |||||||
PG |
Gld | |||||||
P3 |
Y |
|||||||
CM |
Y |
|||||||
P4 |
Y |
Y |
||||||
P3M1 | Y |
Y |
||||||
PMM |
Y |
Y |
Y |
|||||
PMG |
Y |
Gld |
Y |
|||||
PGG |
Y |
Gld |
Gld |
|||||
P6 |
Y |
Y |
Y |
|||||
P31M |
Y |
Y |
Y |
Y |
||||
P4M |
Y |
Y |
Y |
Y |
Y |
Y |
||
P4G |
Y |
Y |
Gld |
Gld |
Y |
Y |
||
P6M |
Y |
Y |
Y |
Y |
Y |
Y |
Y |
Work:
The first part of my project involves improving the accuracy of the existing code that was written for the group identification. I began by running the code on the images in the texture database to identify possible reasons of failure. Some of these were relatively quick-fix -- small errors in the implementation, or a little sharpening of the algorithms, but by and large, the problems (some of which are already pointed out in the paper) seem to stem from the following:
- There is no definite
threshold or method for determining which transformations give a
'good' correlation
score. The paper uses a threshold score of 1.0, while the algorithm
divides the good and bad scores using k-means, with k=2. I'm trying to
find a way to combine the threshold and the clustering methods to get
an efficient determination procedure.
- Many images have large areas of uniformity, with only a small percentage of the pixels
accounting for their characteristic patterns and symmetry (like
the brick background of this page, for instance). Thus, the uniformity
results in the correlation scores being inevitably good for all
transformations. To get rid of this inaccuracy, it's necessary to weigh
the edges in the image
higher, so that they contribute significantly to the correlation.
- A lot of real world textures have shading irregularities, whether caused by natural smudging or shadows. They also might have a lot of color variation that is separate from, and contributes little to, their characteristic patterns. While the human eye might be able to discern the symmetry of the original pattern despite the color haziness, the program, relying as it does purely on correlation of intensity values, cannot always extract this intuitive pattern the way that eye can. This problem is allayed to agreat extent by filtering out noise, but in particularly brightly colored or shadowed images, it becomes harder to separate the two features. I'm hoping to find a way for the program to discard back or foreground shading when there is already a regular pattern present.
This is just an overview. For more detailed and current reports, see my journal or the midproject and final papers.
_____________
[1] A Computational Model for Periodic Pattern Perception Based on Frieze and Wallpaper Groups
Y. Liu, R. Collins, and Y. Tsin
IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 26, No. 3, March, 2004, pp. 354 - 371
[2] Frieze and Wallpaper Symmetry Groups Classification under Affine and Perspective Distortion
Y. Liu and R. Collins
tech. report CMU-RI-TR-98-37, Robotics Institute, Carnegie Mellon University, July, 1998