Exploring a Design Space for Patterns and Tilings

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche

zurück zur Liste der Wettbewerbe zur Evolutionären Kunst


First Exploring a Design Space for Patterns and Tilings Competition 2015

to do:

  • prototiles
  • S(col): Set of possible colorations of prototiles in pattern
  • overlap def
  • gap artefacts at edges with prototile polygons with angles other than {90, 45}
  • alternative/extended approach: tiling pattering with image format that supports layer representation. relaxation of fitness condition overlap → min




Introduction

The goal of this periodic programming competition is to develop methods that can explore a very general but on the other side specific design space of 2 dimensional patterns and tilings (see DS-definition), implement those methods and and apply them to build alongside an open source repository of generation commands for interesting patterns and tilings that could be used directly in image editing by contemporary and future artists, illustrators, designers, ...


To be usefull for image editing purposes geometric construction of patterns and tiles is not sufficient; one must be able to build these structures by prototiles shaped cut-out image parts. This becomes possibe if patterns and tilings are build from prototiles by image processing commands (like CRMT-commands (clone, rotate, mirroring, translate)). Monochrome prototiles can be used in the learning phase where a command list is seachred that builds the pattern but in the application phase a prototile with transparent background will be first used as a mask to cut out a part of an other image and then a pattern is build with such image parts from scratch. Principal examples to such an approach are the implementations of the euclidean symmetry groups by G. Bachelier 2007 with PerlMagick see References & Links.


The search for a tile generation procedure could be thought as a 2D packaging problem with overlap → min ∧ gap → min in combination with a learning/optimaziation procedure to generate a sequence of image processing commands that could build a pattern with given prototiles from scratch. The advantage of this approach is the seperation of learning and application: The learning procedure can be one of the many alternatives from symbolic AI, statistical learning, Neuronal Networks to Evolutionary Computation so a huge number of researchers from diverse fields could potentially participate in this contest. Regarding to the method independent approach this type of competition could be similar to the data science competitions at Kaggle; nevertheless the focus will be on Evolutionary Computation because of the embedding in an Evolutionary Art context.

On the other hand if a command list that generates a pattern is available this list can be used, interpreted and modified in many other programming languages and environments independent of the learning environment.




evidence that Shape Grammars are well suited to represent patterns and tilings (for example: E. Ulu, S. M. ŞENER: A SHAPE GRAMMAR MODEL TO GENERATE ISLAMIC GEOMETRIC PATTERN. In: Generative Art 2009; S. Cenani, G. Cagdas: A Shape Grammar Study: Form Generation with Geometric Islamic Patterns. In: Generative Art 2007) therefore Grammatical Genetic Programming Systems (http://www.grammatical-evolution.org/) would be one obvious choice for a learning environment.


An other approch coud be swarm algorithms were ants are carrying different types of polygons around a plane part, put them down and pick them up at different places following local rules to build patterns. To make this approach efficient the building history must be revised after a pattern is generatet to remove unproductive actions.






Competition terms

In the first Competition the task is to reproduce as much as possible of the known tilings with the CRMT-approach. If the goal would be solely reproducing existing tilings one could use existing algorithms for example in math environments like Mathematica in combination with a general strategy to generate image command lists for any geometrically constructed pattern. But because the goal is more general such approaches should not be honored.

One could use a given source like "B. Wichmann: The world of Patterns" see References & Links as reference for the tile classification and the tile examples.

Each competitor must verify the capability of his approach by submitting a minimum number of $tile_nr_min different tiles.

The winning condition is the maximal number of submitted different tiles.

For the proof of the number of submitted tiles and their verifiability each competitor (person or team) must register in a wiki design_space_of_tiling (to be made) and every submitted tile must be documented there with the given page template.

Every entry in the template (text, code, command lists, images, ...) will be published under a creative commons licence that allow the unrestriced use for all non-commercial and comercial purposes.

Competition start: xx.xx.2015

Competition end: yy.yy.2016

Note to CC licence


Prize money

$$$


Definition of a tile generation task

Given:

  1. One or more basic polygon shapes: $S1 ( ..., $Sn) given as png files where the shape points are touching the canvas boarders and with transparent background. The shapes are monochromatic.
  2. A pattern image $P with width $w_P and height $h_P that should be covered with the shapes.
  3. A set of image processing commands like (clone, rotate, mirror, translate).
  4. A fitness condition (which defines the problem as a 2-objective minimization problem): overlap → min ∧ gap → min.

Note to pattern image - Note to pattern image and image processing commands - Notes to fitness condition


Wanted:

The Pareto front of solution candidates consisting of image processing command lists $comdo_list_j. Each command list consists of 5-tuples $5_tuple_j_k of parameters for the four CRMT commands:

  1. coding of the clone command by using a shape number: {1, ..., n}
  2. coding of the rotate command: [0,360[ degrees
  3. coding of a mirror command: 0 => do nothing, 1 => flip (top-bottum), 2 => flop (right-left)
  4. coding of a translate command with one value for the x-axis and one for the y-axis.

Note to rotation - Note to translation


Example:

A 5-tuple (1, 45, 1, 254, 476) would be interpreted as:

Clone shape S1 => rotate it +45 degree => correct rotation => flip it => translate the shape over the pattern image $P with x=>254 and y=>476

In PearlMagick this would be the following processing pipeline:

$S1 = $Shape_list->[0]->Clone();

$S1->Rotate(degrees=>'45', color=>'transparent');

$S1->Trim();

$S1->Flip();

$Pattern->Composite(image=>$S1, compose=>'over', x=>'254', y=>'476', color=>'transparent', matte=>'true');


Required components

1) Automatic programming environment/Evolutionary algorithm-environment that generates populations of solution candidates.

2) Image-interpreter that generates candidate images from the solution candidates by using a graphic program or library (like Image Magick or OpenGL).

3) Fitness-evaluator that is counting the gap pixels and compute the overlay pixels of the candidate images with the help of the command list.


Procedure

Generate an initial population of solution candidates: $comdo_list_t_0_j, j = 1, ..., n;

Until ($stop_criterion == 0) {

Interprete the solution candidates with the given shapes to generate candidate images: $image_t_j;

Compute the fitness values $gap_j and $overlay_j for every candidate images;

Check the stop criterion;

Reproduction: apply a multi(2)-objective method to generate a new population of solution candidates with the help of the fitness values;

};


Definition of the Pattern Design Space

The combinatorical pattern design space of this idea could be written as the Cartesian product

PDS = S(poly) x S(com) x S(fit) x S($P) x Sdim) x S(geo)

with

  1. S(poly): Set of possible shapes/polygons (if one shape is used) or set of combinations of possible shapes/polygons (if more than one shape is used)
  2. S(com): Set of possible commands (with {clone, rotate, mirror, translate} as the minimal set)
  3. S(fit): Set of possible fitness conditions
  4. S($P): Set of possible sizes of pattern image $P
  5. S(dim): Set of possible dimensions
  6. S(geo): Set of possible geometries

In the first run/runs of this programming competition the Design Space should be constrained:

  1. S(poly) = Set of possible shapes/polygons (if one shape is used) or Set of combinations of possible shapes/polygons
  2. S(com) = {clone, rotate, mirror, translate}.
  3. S(fit) = {overlap → min ∧ gap → min}.
  4. S($P) = {($w_P, $h_P) = f($mult, $w_S_i, $h_S_i | i = 1, …, n)}.
  5. S(dim) = {2}.
  6. S(geo) = {euclidean}.


Public Relation strategy for the Competition

  • Post in online forum
  • Cooperation with conferences
    • EvoMUSART
    • EuroGP
    • GECCO

Notes

Note to CC licence

Note to pattern image

A predefined pattern image $P has the disadvantage that it does not reflect the size of the shape/shapes. A tiling should be large enough that one can see the regularities but it should be restricted because the cost of building a tiling is growing with the size of the pattern. Therefore the width and hight of the pattern image should be a function of the width and height of the shape image (or values if several shapes are used) and a multiplier $mult: ($w_P, $h_P) = f($mult, $w_S, $h_S) or ($w_P, $h_P) = f($mult, $w_S_i, $h_S_i | i = 1, …, n). A 3x3- or 4x4-pattern should be sufficient and for the function one could for example determine th shape with the largest number of pixels and use its width and hight.

Note to pattern image and image processing commands

In the work about the euclidean symmetry groups G. Bachelier used a slightly different approach for the pattern image and the processing commands ( References & Links). The generation process of a tile begins with one shape (equals the pattern image) and this image is successively extended at one of its four edges and then a shape of the same type is rotated, mirrored and translated in one of the edges of the extended image. This means that the tile is growing until it has reached its full size so the command list used in this variant would be (clone, rotate, mirror, extent, translate) (see: http://www.imagemagick.org/Usage/crop/#extent or "Extent" method in http://www.imagemagick.org/script/perl-magick.php). With the parameters width=>integer and height=>integer the new size of the tile part is defined and with gravity=>{NorthWest, North, NorthEast, West, Center, East, SouthWest, South, SouthEast} it is defined where to insert an image part with background=>'transparent'. The advantage of this approch is that one needs only the gravity-parameter with its 8 possible values for the translation instead of the x and y values. Possibly such an extend-approach would be more efficient because it reduces the search space of the optimization problem but on the other side this has the risk of becomming trapped in a local sub-minimum.

Notes to fitness condition

  • This 2-objective minimization is independent of any kind of aesthetic measure. The definition of an appropriate measure for tilings/patterns build with monochrome shapes sould be part of one following competition.
  • The definition of gap is obvious as the number of transparent pixel in a candidate image and can be determined with the result image without the knowlege of the generation process i.e. the command lists. The defition of overlap is more complex and it seems that it requires the resulting candidate image and the command list. There is a sketch of an inductive proof of the overlap measure:

++++++++++++++++++++

for the case of using one shape type and the case of using more than one shape type.


Note to rotation

If a shape is rotated the ratio of the image can increase and the shape is not any more touching the image borders. This has consequences for the following translation because the translation in ImageMagick uses the left upper point as reference for the x- and y-value and uncorrected this would lead to gaps and/or overlaps. To correct this the parameterless IM-method Trim() can be used directly after rotation ($image=>Trim();)

Note to translation

If one uses an interpreter that can not use sub-pixel precision a naive range would be: x: [0, ..., $w_P - 1] and y: [0, ..., $h_P - 1]. But one must allow negative values to compose shapes in a way that the boarder regions of the pattern canvas are covered. Be w_shape_before_translate the width and h_shape_before_translate the height of the shape canvas before the translation the ranges are expanded to x: [-w_shape_before_translate + 1, ..., $w_P - 1], y: [-h_shape_before_translate + 1, ..., $h_P - 1]. (In PerlMagick the translate command would be integrated in a compose_over-command with absolute x and y coordinates.)

Note to 6-Tupel extention approach

Alternatively a 6-Tupel is used for the extention approach:

  1. coding of the clone command by using a shape number: {1, ..., n}
  2. coding of the rotate command: [0,360[ degrees
  3. coding of a mirror command: 0 => do nothing, 1 => flip (top-bottum), 2 => flop (right-left)
  4. coding of an extent command with one parameter for the four sides that is extented side and one for extention measure:
    1. gravity=>{NorthWest, North, NorthEast, West, Center, East, SouthWest, South, SouthEast}
    2. delta-extention.
  5. coding of a translate command with one parameter: gravity=>{NorthWest, North, NorthEast, West, Center, East, SouthWest, South, SouthEast}.


For example a 6-tuple (1, 45, 1, West, 254, West) would be interpreted as:

Clone shape S1 => rotate it +45 degree => correct rotation => flip it => extent the pattern on its right side (West) to 254 pixel with transparent background => translate the shape over the pattern image on the west side


In PearlMagick this would be the following processing pipeline:

$S1 = $Shape_list->[0]->Clone();

$S1->Rotate(degrees=>'45', color=>'transparent');

$S1->Trim();

$S1->Flip();

($p_w, $p_h) = $Pattern->Get('columns', 'rows');

$Pattern->Extent(gravity=>'West', width=>$p_w+254, height=>$p_h, background=>'transparent');

$Pattern->Composite(image=>$S1, compose=>'over', gravity=>'West', color=>'transparent', matte=>'true');


References & Links

  • Descriptions of some euclidean symmetry groups with a clone-rotate-mirror-translate-approach (G. Bachelier 2007): (note: web links in the pdf's are not valid any more)
  1. http://www.vi-anec.de/Trance-Art/IM-examples/IM-plane_group_pmm/pmm_e.pdf
  2. http://www.vi-anec.de/Trance-Art/IM-examples/IM-plane_group_p4m/p4m_e.pdf
  3. http://www.vi-anec.de/Trance-Art/IM-examples/IM-plane_group_p3m1/p3m1_ges_e.pdf
  4. http://www.vi-anec.de/Trance-Art/IM-examples/IM-plane_group_p6m/p6m_e.pdf
  5. http://www.vi-anec.de/Trance-Art/IM-examples/IM-plane_group_p3/p3_e.pdf
  6. http://www.vi-anec.de/Trance-Art/IM-examples/IM-plane_group_p31m/p31m_e.pdf


Tiling Classification in "B. Wichmann: The world of Patterns"

1) Mathematical

1.1) Regular polygons all having the same edge length

1.1.1) The simplest form of tiling pattern with only regular polygons are those known to the Greeks (these have only one type of vertex): Archimedean tilings

1.1.2) The next simplest category of tilings with regular polygons are those with two different types of vertices.

1.1.3) The obvious generalization of the above are those tilings with three different types of vertices.

1.1.4) Tilings formed from tiles which dissect a regular polygon.

1.1.5) Tilings produced just with squares, but having different edge lengths.

1.1.6) Tilings produced just with equilateral triangles, but having different edge lengths.

1.1.7) Tilings produced with a mixture of regular polygons, but having different edge lengths.

1.1.8) Tilings produced with a regular polygon and another polygon having maximal symmetry.

1.1.9) Lastly, other shapes of mathematical interest are collected here.


1.2) Containing mainly regular star polygons all having the same edge length

1.2.1) This part contains regular patterns with star polygons.

1.2.2) This part contains regular tilings with degenerate star polygons with just four sides, ie diamonds.

1.2.3) Other patterns with star polygons.


1.3) Tiling patterns made entirely from one shape: Monohedral Patterns

1.3.1) Tilings in which the single shape is a triangle.

1.3.2) Tilings in which the single shape is a quadrilateral.

1.3.3) Tilings in which the single shape is pentagonal.

1.3.4) Tilings in which the single shape is hexagonal.

1.3.5) Tilings formed by joining equilateral triangles together.

1.3.6) Tilings formed by joining squares together.

1.3.7) Tilings formed by joining regular hexagons together.

1.3.8) Other convex monohedral tilings.

1.3.9) Tilings having a central point.

1.3.10) For most single tiles which tile the plane, the same shape can tile the plane infinitely many ways. For some tiles, the number of ways is limited to 1, 2, etc up to a maximum of 12.

1.3.11) Several beautiful patterns are made by tiling the plane in a spiral design.

1.3.12) Lastly, other shapes of mathematical interest are collected here, including those designed for their artistic effect.


1.4) Patterns defined by the symmetry classes of the vertices and tiles: Homeohedral Tilings

1.4.1) 2-homeohedral tilings.

1.4.1) Others.


1.5) Other shapes of mathematical interest

1.5.1) Patterns made from polygons which can tile the plane in a limited number of ways (due to P Schmitt).

1.5.2) Monohedral tilings with regular vertices.

1.5.3) Tilings made only from infinite lines.

1.5.4) Tilings made from recursive defined patterns.

1.5.5) Others.


2) Artistic

2.1) Pre-Islamic

2.1.1) Roman

2.1.2) Celtic

2.1.3) Those collected by F M Hessemer (which actually covers Arabic and Italian sources)

2.1.4) Those collected by Carol Grafton (which actually later but are mainly in the Byzantine style)

2.1.5) Those collected by Robert Field from churches

2.1.6) Other earlier patterns


2.2) Islamic

2.2.1) J Bourgoin

2.2.2) I El-Said and A Parman

2.2.3) David Wade

2.2.4) S J Abas and A S Salman

2.2.5) Mirza Akber

2.2.6) The Iranian collection

2.2.7) Tilings with a grill design. These are mainly derived from window and door grills

2.2.8) Tilings from the Topkapi Roll

2.2.9) Tilings which are at two levels

2.2.10) Robert Field

2.2.11) Other sources


2.3) Post-Islamic

2.3.1) Quilt patterns

2.3.2) Lattice patterns

2.3.3) Other patterns


zurück zur Liste der Wettbewerbe zur Evolutionären Kunst

Abgerufen von „http://de.evo-art.org/index.php?title=Exploring_a_Design_Space_for_Patterns_and_Tilings&oldid=2762“