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

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche
(→‎Future Directions)
Zeile 13: Zeile 13:
  
 
Other examples for such an approach are the implementations of the euclidean symmetry groups by [[Günter Bachelier | G. Bachelier]] 2007 with [http://www.imagemagick.org/script/perl-magick.php PerlMagick] see [[#References_.26_Links | References & Links]].  
 
Other examples for such an approach are the implementations of the euclidean symmetry groups by [[Günter Bachelier | G. Bachelier]] 2007 with [http://www.imagemagick.org/script/perl-magick.php PerlMagick] see [[#References_.26_Links | References & Links]].  
 +
 +
 +
Photoshop filter Terrazzo from Xaos Tools or the Photo Tiling Tool Pavimenta (António Salgueiro: [[Pavimenta: A Photo Tiling Tool]]. In: [[Bridges 2011]]. Pages 515–518 http://archive.bridgesmathart.org/2011/bridges2011-515.html http://archive.bridgesmathart.org/2011/bridges2011-515.pdf)
  
 
   
 
   

Version vom 5. Februar 2015, 13:53 Uhr

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


Under Construction Under Construction Under Construction Under Construction Under Construction Under Construction Under Construction

Inhaltsverzeichnis

Introduction

The goal of this periodic programming competition is to develop methods that can explore a very general but on the other hand specific design space of patterns and tilings (see DS-definition), implement those methods and and apply them to built 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 appropriate open source license.

In image editing a mathematical compass and straight-edge construction approach is not helping. One must be able to built these structures by prototiles shaped cut-out image parts. For example: The red triangle on transparent background in the figure below is the prototile that builts the p3m1 symmetry group. To built a tile with it would lead to a red image (possible with some gaps) which is good for counting possible gap pixel but not so useful for image editing porposes. Therefore the red shape is used as a mask together with a parent image; with the right type of compositing function a triangle part of the parent image is cut out (p3m1_G1); again with transparent background. With such a prototile a pattern generation in image editing makes sense and could done by a sequence of image processing commands (CRMT-commands: clone the prototile, rotate it, mirror it, translate it over a pattern image to a specific position).

P3m1 Prototile.png

Other examples for such an approach are the implementations of the euclidean symmetry groups by G. Bachelier 2007 with PerlMagick see References & Links.


Photoshop filter Terrazzo from Xaos Tools or the Photo Tiling Tool Pavimenta (António Salgueiro: Pavimenta: A Photo Tiling Tool. In: Bridges 2011. Pages 515–518 http://archive.bridgesmathart.org/2011/bridges2011-515.html http://archive.bridgesmathart.org/2011/bridges2011-515.pdf)


The search for a tile generation procedure could be thought as a 2D packing problem with overlap → min ∧ gap → min in combination with a learning/optimization procedure to generate a sequence of image processing commands that could built 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 from prototiles is available this list can be used, interpreted and modified in many other programming and script languages 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.

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 accepted. On the other hand 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 Tiling Classification) 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 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 prototiles. 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-tuple extension approach
  4. A fitness condition: overlap → min ∧ gap → min (which defines the problem as a 2-objective minimization problem). Notes to fitness condition


Wanted:

The Pareto front of solution candidates consisting of image processing command lists $comdo_list_j regarding to the 2-objective minimization problem overlap → min ∧ gap → min (graphical each solution is a point in a cartesian coordinate system with one axis is the gap measure and the other is the overlap measure). 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 prototile 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 ($S, $r, $m, $x, $y) = (1, 45, 1, 254, 476) would be interpreted as:

Clone prototile S1 => rotate it +45 degree => correct rotation offset ( Note to rotation) => flip it => translate the prototile 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 overlapping pixels of the candidate images with the help of the command list.


Procedure

The following over all pseudo code assumes that the fitness evaluation can be done after a candidate image was generated and did not need to be inside the image generation process. Because of the lack of a technical definition of an overlap measure that can be computed only with the result image and the corresponding command list it is unclear if this kind of procedure is possible.

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 $overlap_j for every candidate image;

Check the stop criterion;

if ($stop_criterion == 0) {Use the EvoAlgo environment for reproduction: apply a 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 prototiles that are generating a known tile or set of combinations of prototiles that are generating together a known tile.
  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 especially by adding an appropriate aesthetic measure for tilings and patterns: S(fit) = {overlap → min ∧ gap → min ∧ F(aest) → max}.
  • Experiments with prototile sets that do not fit exactly together i.e. tiles and pattern with known gaps (and/or overlaps) that are nevertheless interesting and aesthetic (tile'ish patterns). The fitness condition must be modified in this cases from a minimization to a sufficency condition and possibly an appropriate aesthetic measure would be needed to explore this Design Subspace automatically.
  • 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 with the opportunity to explore the aesthetics of 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 generating 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 hand 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 built 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 must quantify the number of pixels of the pattern image that are covered more than one time during the generation process. The question is if such a measure can be computed with the result image and the command list or must it be computed during the generation process. The later requires the integration of the Fitness-evaluator in the Image-interpreter.

The overlap of two shapes can be thought as the intersection of two point sets which is in ImageMagick implemented by the set theoretic compositing method "Darken" (http://www.imagemagick.org/Usage/compose/#set_theory). The computing of the overlap in this case would require a second parallel generation process with compose_darken besides the generation process with compose_over. Every compose operation is made with compose_over for the generation of the result image and with compose_darken for the computing of the overlap measure. The measure would be the sum of the pixels of each intersection during the processing of the command list.

Given is a pattern image $P with width $w_P and height $h_P. In the beginning (t=0) $P is empty i.e. all pixel are transparent resulting in the notation $P_0. Given is also a command list with m 5-tuples ($S, $r, $m, $x, $y). From the command list the sequence @C_S = ($S | j = 1, …, m) of prototiles is extracted as the list of shapes that will be step by step composed independant if there is only one or more prototile types given.

In step t=1 the fist element from @C_S undergo a rotate and mirror transformation with the corresponding parameters $r_1 and $m_1 resulting in $S_1. $S_1 is then composed_over $P_0 with the transition parameters $x_1 and $y_1 resulting in $P_1. Because $P_0 was empty the overlap measure $overlap_1 in step 1 is always zero and the gap measure $gap_1 is computed as the number of non transparent pixels in $P_1 (if this is necessary). In step t=2 the second element from @C_S is transformed with $r_2 and $m_2 resulting in $S_2 and composed_over $P_1 with $x_2 and $y_2 resulting in $P_2 which could lead to an overlap. To compute $overlap_2 $P_1 is cloned and denoted as $P_1_d and $S_2 is composed_darken over $P_1_d with $x_2 and $y_2 resulting in $P_2_d. The overlap $overlap_2 is the number of non transparent pixel in $P_2_d equal to the number of non transparent pixels in the intersection of $P_1_d and $S_2. The overlap values could be pushed in a list @overlap_list which has after processing the whole command list m elements. The overlap measure of the whole generation process of the result image $P_m would be the sum of all m overlap values in @overlap_list.

Is it possible to make an overlap measure that can be computed given the result pattern image and the command list without the m intermediate steps? => Discussion page

Perhaps it is even not necessary to have such an absolute overlap measure that counts the actual pixels that are covered more than one time in the generating process of a pattern/tiling if such a measure is used in a fitness evaluation context. Possibly some kind of relative fitness value would be enough to make a fitness ranking of candidates to implement a selection strategy for reproduction,

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.)
  • A decision must be made if absolute pixel positions in an pattern image should be used like in the 5-tuple example (1, 45, 1, 254, 476) or relative values regarding to the width and height of the pattern image like (1, 45, 1, 0.08467, 0.15867) if a 3000x3000 pixel pattern image is given (0.08467 = 254/3000).
  • 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-tuple 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-tuple:

  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, internal link
  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"

Mathematical

Regular polygons all having the same edge length

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

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

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

Tilings formed from tiles which dissect a regular polygon

Tilings produced just with squares, but having different edge lengths

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

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

Tilings produced with a regular polygon and another polygon having maximal symmetry

Lastly, other shapes of mathematical interest are collected here

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.


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.


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

1.4.1) 2-homeohedral tilings.

1.4.1) Others.


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.


Artistic

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


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


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=4425“