Exploring a Design Space for Patterns and Tilings Competition 2015: Unterschied zwischen den Versionen

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche
Zeile 168: Zeile 168:
 
** https://independent.academia.edu/G%C3%BCnterBachelier
 
** https://independent.academia.edu/G%C3%BCnterBachelier
  
 +
 +
=Future Directions=
 +
* Experiments with other fitness conditions for example adding an appropriate aesthetic measure for tilings and patterns: S(fit)  = {overlap → min ∧ gap → min ∧ F(aest) → max}.
 +
 +
* prototile sets that not fitting exactly together i.e. tiles with known gaps that are nevertheless interesting and aesthetic. This needs an appropriate aesthetic measure.
 +
 +
* Experiments with additional image processing commands: scale; affine matrix transformation or more general the distortion transformations in ImageMagick with affine and lots of other parameters (http://www.imagemagick.org/Usage/distorts/): Affine, AffineProjection, ScaleRotateTranslate SRT, Perspective, PerspectiveProjection, BilinearForward, BilinearReverse, Polynomial, Arc, Polar, DePolar, Barrel, BarrelInverse, Shepards, Resize. Even with an added scaling command there are [http://en.wikipedia.org/wiki/Iterated_function_system iterative function systems IFS] possible to explore the aesthetics self similarity within the design space approach.
  
  

Version vom 5. Januar 2015, 22:37 Uhr

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

to do:

  • overlap def in "Notes to fitness condition"
  • translation: absolute or relative (to pattern image) coordinates?
  • alternative/extended(/simplified?) 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 a repository of generation commands for interesting patterns and tilings that could be used directly in image editing by contemporary and future artists, illustrators, designers, ... under an open source license.


To be useful 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 possible 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/optimization 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 separation 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.


There is 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 would be one obvious choice for a learning environment. An other approach could be swarm algorithms were ants are carrying different types of prototiles around on a plane part, put them down and pick them up at different places following local rules to build patterns where the learning task is to evolve a rule set that generates a specific tiling.


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 exploring a design space such approaches should not be honored. On the other side Evolutionary Algorithms are in some cases implemented in math environments like Christian Jacobs Evolvica for Mathematica so exploring the design space with Evolutionary Algorithms in such an math environment would 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_for_patterns_and_tilings (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 license that allow the unrestricted use for all non-commercial and commercial purposes. Note to CC license
  • Competition start: xx.xx.2015
  • Competition end: yy.yy.2016


Prize money

$$$


Definition of a tile generation task

Given:

  1. One or more prototiles (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. Notes to pattern image
  3. A set of image processing commands like (clone, rotate, mirror, translate). Note to pattern image and image processing commands- Note to 6-Tupel extension approach
  4. A fitness condition (which defines the problem as a 2-objective minimization problem): overlap → min ∧ gap → min. 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. Note to rotation
  3. coding of a mirror command: 0 => do nothing, 1 => flip (top-bottom), 2 => flop (right-left).
  4. coding of a translate command with one value for the x-axis and one for the y-axis. Notes to translation


Example:

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

Clone prototile 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

Use the Evolutionary Algorithm-environment to generate an initial population of solution candidates: $comdo_list_t_0_j, j = 1, ..., n;

Until ($stop_criterion == 0) {

Use the Image-interpreter with solution candidates and given prototiles as input to generate candidate images: $image_t_j;

Use the Fitness-evaluator to compute the fitness values $gap_j and $overlay_j for every candidate image;

Check the stop criterion;

if ($stop_criterion == 0) {Use the EvoAlg environment for reproduction: apply a multi(2)-objective method to generate a new population of solution candidates $comdo_list_t+1_j, j = 1, ..., n with the help of the fitness values} else {stop};

};


Definition of the Pattern Design Space

The combinational 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 S(dim) x S(geo)

with

  1. S(poly): Set of possible prototiles (if one prototile is used) or set of combinations of possible prototiles (if more than one prototile is used) Note on pattern coloring
  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 prototiles (if one prototile is used) or set of combinations of possible prototiles (if more than one prototile is used)
  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


Future Directions

  • Experiments with other fitness conditions for example adding an appropriate aesthetic measure for tilings and patterns: S(fit) = {overlap → min ∧ gap → min ∧ F(aest) → max}.
  • prototile sets that not fitting exactly together i.e. tiles with known gaps that are nevertheless interesting and aesthetic. This needs an appropriate aesthetic measure.
  • Experiments with additional image processing commands: scale; affine matrix transformation or more general the distortion transformations in ImageMagick with affine and lots of other parameters (http://www.imagemagick.org/Usage/distorts/): Affine, AffineProjection, ScaleRotateTranslate SRT, Perspective, PerspectiveProjection, BilinearForward, BilinearReverse, Polynomial, Arc, Polar, DePolar, Barrel, BarrelInverse, Shepards, Resize. Even with an added scaling command there are iterative function systems IFS possible to explore the aesthetics self similarity within the design space approach.


Notes

Note to CC license

Notes to pattern image

  • Mathematical tile generation algorithms are in principle able to generate a pattern with any width x hight. The search for a program (with a Genetic Programming environment) that is able to generate an image command list for pattern generation for an arbitrary pattern size is more complex than the search for a program that generates a command list for only one specific image size. Therefore one should restrict the underlaying problem to the later case.
  • A predefined pattern image $P has the disadvantage that it does not reflect the size of the prototile/s. A pattern should be large enough that one can see the regularities but it should be restricted because the cost of building is growing fast 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 prototile/s 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 (for periodical tilings) should be sufficient and for the function with prototiles one could for example determine the prototile 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 approach 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 becoming 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 knowledge of the generation process i.e. the command lists. The definition 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();)

Notes 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.)
  • If an image-interpreter is used which relies on a graphic program or library that can not use subpixel accuracy it is shown (in PerlMagick implementations of the euclidean symmetry groups) that gap artefacts could be generated at edges where the prototile polygons fit together. This is often the case if the polygons have other angles than {90, 45}°. If such tiles or patterns are saved in file formats that did not support transparency like jpg the gap pixel are set to black which result in viewable artefacts. A simple image editing heuristic was developed to fill all the gap pixel with local content by compose=>'over' the pattern over a slightly enlarged version of itself. In the case of the fitness evaluation it might be reasonable to distinguish between such gap pixel lines that can be corrected in image editing contexts and two-dimensional gap defects that can not locally corrected.

Note to 6-Tupel extension approach

Alternatively an approach could be used that begins with one prototile (with transparent background) and iteratively extend the image until the given width and hight of the pattern is reached. This requires and additional image processing command (Extent()) and results in a 6-Tupel:

  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-bottom), 2 => flop (right-left)
  4. coding of an extent command with one parameter for the side that is extended and one for extension measure:
    1. gravity=>{NorthWest, North, NorthEast, West, Center, East, SouthWest, South, SouthEast}
    2. delta-extension in pixel.
  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 prototile 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');

$p_w_new = $p_w + 254;

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

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

Note on pattern coloring

The prototiles in mathematical constructions of tiles are first of all monochrome with one color independent if one or more prototile types are used. There are many ways to color a pattern by assigning different colors to a prototile at different positions of the pattern or different colors to different types of prototiles. The set of possible coloring algorithms could be an additional dimension of the design space but for to underlying goal of using patterns for image editing this is not necessary. One can substitute a coloring rule system by enlarging the set of prototiles so that every color correspond to new added prototile type. If for example a tiling is used with one prototile and a coloring rule system with three colors one could enlarge the set of prototiles to three.


References & Links

  • Descriptions of some euclidean symmetry groups with a modified 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_Competition_2015&oldid=2879“