Exploring a Design Space for Patterns and Tilings Competition 2015
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
- 1 Introduction
- 2 Competition terms
- 3 Prize money
- 4 Definition of a pattern generation task
- 5 Required components
- 6 Procedure
- 7 Definition of the Pattern Design Space
- 8 Public Relation strategy for the Competition
- 9 Future Directions
- 10 Notes
- 11 References & Links
- 12 Tiling Classification in "B. Wichmann: The world of Patterns"
- 12.1 Mathematical
- 12.1.1 Regular polygons all having the same edge length
- 12.1.2 Containing mainly regular star polygons all having the same edge length
- 12.1.3 Tiling patterns made entirely from one shape: Monohedral Patterns
- 12.1.4 Patterns defined by the symmetry classes of the vertices and tiles: Homeohedral Tilings
- 12.1.5 Other shapes of mathematical interest
- 12.2 Artistic
- 12.1 Mathematical
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 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 equilateral triangle on transparent background in the figure below is the prototile that assembles the p3m1 symmetry group image. 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 purposes. 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).
As a prove of concept there are reference implementations for several tiles of the euclidean symmetry groups with the CRMT-approach (see the following four images); for older examples of implementations of the euclidean symmetry groups with non CRMT methods by G. Bachelier 2007 with PerlMagick see References & Links.
- pmm Reference Implementation
- p4m Reference Implementation
- p3m1 Reference Implementation
- p6m Reference Implementation
There are (or were) software that are using tiles in image editing like the Photoshop filter Terrazzo from Xaos Tools, the Photo Tiling Tool Pavimenta (António Salgueiro: Pavimenta: A Photo Tiling Tool. In: Bridges 2011. Pages 515–518) and the GIMP filter Texturize. The first two were not available any more and they were only using the 17 euclidean symmetry groups of the plane and none of the diversity of the other tiling methods. There is also the possibility to make tilings in vector graphic programs like Illustrator (here) and Inkscape (here), but again only the 17 symmetry groups were available.
The search for a pattern 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. Or it can be viewed as a puzzle solving problem were the prototiles are the puzzle elements that are moved over a plane and put together to built tilings and patterns.
An Evolutionary Algorithm environment could process this 2D packing problem like a physical puzzle (dissection puzzle, Tangram, T puzzle, tiling puzzle, eternity puzzle, geometric magick square, jigsaw puzzle). A complex example is the physical "Zellij Multipuzzle" (Jean Marc Castera: Zellij Multipuzzle. In: Bridges 2006. Pages 665–666), which implements a puzzle based on Islamic tilings and ornaments with an extreme number of 21 prototile types (see following images from Castera: Zellij Multipuzzle) and a total number of 669 prototiles (plus different boarder pieces) where one side is colored in white, the other in a different color. The task is to pack a number of prototiles together with no gap and overlap. In the case of the Zellij Multipuzzle there is a large design space of configurations with and without symmetries that satisfy this condition which means that they are all in the Pareto front of this 2-objective problem "overlap → min ∧ gap → min" and the Evolutionary Algorithm environment should be able to return all of the elements in the Pareto front.
The advantage of the command list 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 is similar to the data science competitions at Kaggle. Nevertheless the focus should be on Evolutionary Computation because of the embedment in an Evolutionary Art context (also this should not be excluded for later competitions). On the other hand if a command list that generates a pattern from prototiles is available an image interpreter can use this list (and modified it) in every other programming and script language independent of the learning environment. And because the elements in the command list are logically independent from another they can be parallelized on this level which is of use especially if the image operations are also parallelized like in a programming language that can use the GPU (like OpenGL, Vulkan, OpenVG or OpenCL).
There is evidence that Shape Grammars are well suited to represent patterns and tilings (for example: Ulu & ŞENER: A SHAPE GRAMMAR MODEL TO GENERATE ISLAMIC GEOMETRIC PATTERN. In: Generative Art 2009; Cenani & 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 built an learning environment (or Evolutionary Algorithms environment) that can reproduce as much as possible of the known tilings with the command list approach. The environment and the settings must be made public available without any restrictive licensing.
- In a first step the prototile or prototiles of a known tiling/pattern were identified based on an image for example retrieved from "B. Wichmann: The world of Patterns" (see Tiling Classification) or from the Tiling Database also with Brian Wichmann. This could be done by human expertise, interactively or automatic if a good enough tile image is given. Automatic approaches must have some knowledge about euclidean geometry to correct measured angles and length. It is quite a task in experimental mathematics to deduce from measures to closed forms.
- If the additional condition is given that a tile image should be reproduced exactly one can not only identify the types of prototiles but also the number of each prototile type. With this information an obvious stop criteria would be the use of all the members in the given prototile set.
- In a second step prototile images were generated were monochrome prototiles are exactly drawn on a transparent background with no borders. The width and height measures of the prototiles must be balanced so that they fit together and could built a tile or pattern. The width and height of the prototile images define the width and height of the pattern image (see the Notes to pattern image). If a prototile is specified by one length (like the width of a equilateral triangle in the p3m1 case), the length should be specified with 1000 pixels.
- If the general 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 CRMT command lists for any geometrically constructed pattern. But because the wider 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.
- Each competitor (person or team) must verify the capability of his approach by submitting a minimum number of different tiles from different tile classes from "B. Wichmann: The world of Patterns" or the Tile Database (number of tiles and number of tile classes must be specified).
- The winning condition is the maximal number of submitted different tiles from different tile classes.
- 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 (template sketch must be further specified).
- Every entry in the template (text, code, command lists, images, ...) is published under a creative commons license that allow the unrestricted use for all non-commercial and commercial purposes for contemporary and future artists, illustrators, designers, ... Note to CC license
- Competition start: 15.04.2015
- Competition end: 15.01.2016
- Announcement of the winner: 15.04.2016
Prize money
The winner of the first competition will get a money price of minimum 500 EUR (dependent if addition sponsors are filling in).
Definition of a pattern generation task
Given:
- 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.
- A pattern image $P with width $w_P and height $h_P that should be covered with the prototiles. Notes to pattern image
- 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
- 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 6-tuples $6_tuple_j_k of parameters for five CRMT commands:
- coding of the clone command by using a prototile number that refers to a prototile in an image list $Shape_list: {0, ..., n}.
- coding of the rotate command: [0,360[ degrees. Note to rotation
- coding of a mirror command Flop: Fo.
- coding of a mirror command Flip: Fi.
- coding of a translate command with one value for the x-axis and one for the y-axis in one ($T) or two separate commands ($x, $y). Notes to translation
Example implementations show that we must use a flexible coding scheme regarding the positions of the rotate and mirror commands because there are some combinatorial cases to consider that must be distinguished because the image processing commands are in general not commutative (the sequence matters). This means that a simple coding scheme with fixed positions like ($C, $Fo, $R, $Fi, $x, $y) can not be used.
First of all one can say that the position of the clone and the compositing command is fixed: it is the first and last place in the command list. Regarding the rotate and the two mirror commands the following combinations are possible (including the first case were none of them were applied):
($C, $x, $y), ($C, $R, $x, $y), ($C, $Fo, $x, $y), ($C, $Fi, $x, $y), ($C, $Fo, $R, $x, $y), ($C, $R, $Fo, $x, $y), ($C, $Fi, $R, $x, $y), ($C, $R, $Fi, $x, $y), ($C, $Fo, $Fi, $R, $x, $y)=($C, $Fi, $Fo, $R, $x, $y), ($C, $R, $Fo, $Fi, $x, $y)=($C, $R, $Fi, $Fo, $x, $y), ($C, $Fo, $R, $Fi, $x, $y), ($C, $Fi, $R, $Fo, $x, $y)
Therefore it is necessary to also code the type of command like 'C' for clone, 'R' for rotate, 'Fo' for Flop, 'Fi' for Flip, 'x' for x-translation and 'y' for x-translation.
The next fact that must be included is the use for parameters with the C, R, x, and y command:
$C = 'C' . $prototile_nr;
$R = 'R' . $rotation_degree;
$x = 'x' . $x_value;
$y = 'y' . $y_value; (or $T = 'T' . '_' . $x_value . '_' . $y_value;)
With this components a flexible coding is possible that consider all possible positions of the commands. For example (C0, Fo, R-60, Fi, x250, y0) is coding the following processing pipeline:
- Clone first prototile in image list (when list numbering starts with 0)
- Flop
- rotate it -60 degree (plus additional correction of rotation offset ( Note to rotation))
- Flip
- composing_over with x-value of 250 and y-value of 0
In PearlMagick this would be implemented as (see for details the reference implementation of a p3m1-tile):
$prototile_crm = $Shape_list->[0]->Clone(); $prototile_crm = Flop(); $prototile_crm->Rotate(degrees=>'-60', color=>'transparent'); $prototile_crm->Trim(); $prototile_crm->Flip(); $tile->Composite(image=>$prototile_crm, compose=>'over', x=>'250', y=>'0', 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
- 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
- S(com): Set of possible commands (with {clone, rotate, mirror, translate} as the minimal set)
- S(fit): Set of possible fitness conditions
- S($P): Set of possible sizes of pattern image $P
- S(dim): Set of possible dimensions
- S(geo): Set of possible geometries
In the first run/runs of this programming competition the Design Space should be constrained:
- S(poly) = Set of prototiles that are generating a known tile or set of combinations of prototiles that are generating together a known tile.
- S(com) = {clone, rotate, mirror, translate}.
- S(fit) = {overlap → min ∧ gap → min}.
- S($P) = {($w_P, $h_P) = f($mult, $w_S_i, $h_S_i | i = 1, …, n)}, for example: $mult = 4, $w_P = $mult * max($w_S_i | i = 1, …, n), $h_P = $mult * max($h_S_i | i = 1, …, n).
- S(dim) = {2}.
- S(geo) = {euclidean}.
Public Relation strategy for the Competition
- Mail in general Evo Algo mailing lists
- EC Digest The Evolutionary Computation Mail Digest: http://ec-digest.research.ucf.edu/ EC-Digest-l@listserv.gmu.edu
- Yahoo GP news group: https://groups.yahoo.com/neo/groups/genetic_programming/info
- Mail in mailing lists of Evo Algo software
- ECJ (Java, http://cs.gmu.edu/~eclab/projects/ecj/): https://listserv.gmu.edu/cgi-bin/wa?SUBED1=ecj-interest-l&A=1
- EO Evolutionary Computation Framework (C++, http://eodev.sourceforge.net/): https://lists.sourceforge.net/lists/listinfo/eodev-main eodev-main@lists.sourceforge.net
- Beagle - Open BEAGLE (C++, http://code.google.com/p/beagle/): http://groups.google.com/group/openbeagle-users
- Deap (Python, http://code.google.com/p/deap/): https://groups.google.com/forum/#!forum/deap-users
- HeuristicLab (?, http://dev.heuristiclab.com/): https://groups.google.com/forum/#!forum/heuristiclab
- Watchmaker (Java, http://watchmaker.uncommons.org/): https://groups.google.com/forum/#!forum/watchmaker
- Twitter
- Deap (http://code.google.com/p/deap/): https://twitter.com/deapdev
- BridgesMathArt: https://twitter.com/BridgesMathArt
- MathArt: https://twitter.com/hashtag/MathArt
- GenerativeArt: https://twitter.com/generativeart
- AlgorithmicArt: https://twitter.com/hashtag/algorithmicart
- https://twitter.com/lumenprize
- Scientific Social Networks (ask question, make post, make announcement, ...)
- Post in online forum
- Cooperation with blogger
- Cooperation with conferences
- EvoMUSART 2015 http://www.evostar.org/2015/cfp_evomusart.php Conference chairs: Colin G. Johnson (c.g.johnson ät kent.ac.uk), Adrian Carballal (adriancarballal ät gmail.com)
- EuroGP 2015 http://www.evostar.org/2015/cfp_eurogp.php Programme Chairs: Penousal Machado (machado ät dei.uc.pt), Malcolm Heywood (mheywood ät cs.dal.ca)
- GECCO
- Cooperation with journals
- Evolutionary Computation http://www.mitpressjournals.org/loi/evco http://www.researchgate.net/journal/1530-9304_Evolutionary_Computation
- Genetic Programming and Evolvable Machines http://www.springer.com/computer/ai/journal/10710 http://gpemjournal.blogspot.de/ http://www.researchgate.net/journal/1389-2576_Genetic_Programming_and_Evolvable_Machines
- Swarm and Evolutionary Computation http://www.journals.elsevier.com/swarm-and-evolutionary-computation/ https://www.researchgate.net/journal/2090-4908_International_Journal_of_Swarm_Intelligence_and_Evolutionary_Computation
- Journal of Mathematics and the Arts http://www.tandfonline.com/toc/tmaa20/current#.VKU6FNegMhc https://www.researchgate.net/journal/1751-3472_Journal_of_Mathematics_and_the_Arts
- Cooperation with scientific societies
- SIGEVO - ACM Special Interest Group on Genetic and Evolutionary Computation http://sigevo.hosting.acm.org/wiki/tiki-index.php http://www.sigevolution.org/ https://www.researchgate.net/journal/1931-8499_ACM_SIGEVOlution Contact: Wolfgang Banzhaf (banzhaf ät mun.ca)
Future Directions
Fitness functions
Experiments with other fitness conditions especially adding appropriate aesthetic measures for tilings and patterns: S(fit) = {overlap → min ∧ gap → min ∧ F(aest) → max}.
Image manipulator
Extend the image interpreter to an image manipulator that manipulates the CRMT command lists and/or the associated list with prototiles/shapes. A design space of possible types of manipulations could be developed and this space could be explored with evolutionary methods, which requires again aesthetic fitness measures if such an exploration should be done automatically. This approach has connections to the tile'ish patterns below. Two use cases should be described: black and white (or gray scale) prototiles and color prototiles.
- If black and white prototiles are used it doesn't matter if large gap artifacts arises if a prototile is rotated or translated because such a black region is becoming part of the black background (if the result is written in jpg). Such black and white patterns could be used as masks for color images and the outcome of the command list manipulations are interesting mask variants with conserved or broken symmetry.
- If color prototiles are used large black region can be considered as aesthetically disruptive. In such a case a colorized background should be used perhaps the pattern that arises from the non manipulated CRMT command list, a transformed version of this, or a pattern with other color prototiles.
Example: If there is a symmetric black and white tile/pattern is used like a p3m1-tile with its top-bottom symmetry two corresponding local CRMT command lists are identified and manipulated accordingly for example by translating the top triangle more to the top and the bottom triangle more to the bottom. In this case the symmetry is preserved but in the same time the symmetry of the p3m1-tile becomes broken.
Non fitting prototiles
Experiments with prototile sets that do not fit exactly together viz 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 sufficiency condition and possibly an appropriate aesthetic measure would be needed to explore this design subspace automatically.
Finite subdivision rules
Reverse approach by Finite subdivision rules: Given is a shape that acts like the pattern image $P with a given tiling. A subdivision rule changes that tiling by subdividing the given polygon into smaller polygons which can be continued iteratively. After a stop criteria holds the given tiling is analyzed (by hand, interactively or automatic) to identify the polygon types (prototiles) and the number of each type that built together the tile. Then a tile learning procedure (from previous iterations of the competition) generates a command list that pushes the prototiles together so that the tiling can be used for image editing purposes. The use of evolutionary computation can be twofold here: First a Genetic Programming approach can search for subdivision rules with interesting and aesthetic results and in the second step an evolutionary algorithm search for a command list that reproduces the pattern from the given prototile set.
Generalized Tangrams
Explore relationships to generalized tangram: Generating of prototiles by subdivision of a shape and searching for interesting/aesthetic configurations of the prototiles within a larger pattern image (no gap → min condition).
Vector graphics
Experiments with vector graphics: There are possibilities to script vector objects in Inkscape: Four ways to generate or process Inkscape vector graphics automatically. With --verb on the command line Inkscape can process basic geometric commands like --verb ObjectFlipVertically, but because the verb-approach can not process parameters it is not yet clear if this approach is directly powerful enough to interpret the CRMT-lists. But SVG images are defined in XML files therefore components of vector objects and their behavior can be edited with text editors so methods and parameters could be specified on this way. In conclusion it seems plausible that a CRMT-vector-image-interpreter could be made, that takes a vector object in the shape of a prototile and a CRMT-command list and generates a tile or pattern.
Inkscape has the ability to generate tiles but again restricted to to plane groups. With the use of CRMT-lists the large design space of tilings and pattern could be used in vector graphic formats.
Inkscape is able to cut out vector image parts with the Clipping and Masking methods. If a clipping path is shaped like a polygon it can be used to generate a color prototile that a CRMT-command list transforms to a tile or pattern.
Additional processing commands
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 general design space approach.
Ornament deformations
Parquet/ornament deformations (see Craig S. Kaplan: Computer Graphics and Geometric Ornamental Design, pp. 57): Searching for interesting/aesthetic mathematical deformation functions, analyzing the deformed ornaments to identify the polygon types (prototiles) and the number of each type that built together the ornament just like in the case of the Finite subdivision rules. Then using a pattern learning procedure that can reproduce the deformed ornament with CRMT-command lists. Again evolutionary computation can be used for searching deformation functions and for the learning process whereat the number of prototile types could become very large because every layer of the parquet has slightly different types and therefore the number is also dependent of the range of the parquet.
Notes
Note to CC license
- CC0 Public Domain https://creativecommons.org/choose/zero/?lang=en
- CC4.0 http://creativecommons.org/licenses/by/4.0/ http://creativecommons.org/licenses/by/4.0/legalcode https://creativecommons.org/choose/ Usage with "appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.")
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 should 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 viz 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 independent 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? => Overlap Measure
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 CRMT-tuples or relative values regarding to the width and height of the prototile if only one prototile is used or the width and height of tile/pattern image.
- 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 artifacts 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 artifacts. 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:
- coding of the clone command by using a prototile number that refers to a prototile in an image list $Shape_list: $C = 'C' . $prototile_nr; $prototile_nr from {0, ..., n}.
- coding of the rotate command: $R = 'R' . $rotation_degree; $rotation_degree from [0,360[.
- coding of a mirror command Flop: $Fo.
- coding of a mirror command Flip: $Fi.
- coding of an extent command with two parameters: $E = 'E' . $gravity . '_' . $extention_value.
- gravity=>{North, West, East, South}. (simplified list of gravity options)
- delta-extension in pixel.
- coding of a translate command for the composite command : $T = 'T' . '_' . $gravity (or $xy = 'xy'. . $gravity).
- gravity=>{NorthWest, North, NorthEast, West, Center, East, SouthWest, South, SouthEast}. (full list of gravity options)
For example a 6-tuple (C0, Fo, R-60, Fi, E_West_250, T_West) would be interpreted as:
- Clone first prototile in image list (when list numbering starts with 0).
- Flop.
- rotate it -60 degree (plus additional correction of rotation offset).
- Flip.
- extent the tile on the left side (= west) of 250 pixels.
- composing the prototile over the tile and set the prototile at the left boarder of the tile (= geometry: West).
In PearlMagick this would be implemented as:
$prototile_crm = $Shape_list->[0]->Clone(); $prototile_crm = Flop(); $prototile_crm->Rotate(degrees=>'-60', color=>'transparent'); $prototile_crm->Trim(); $prototile_crm->Flip(); ($w, $h) = $tile->Get('columns', 'rows'); $w_new = $w + 250; $tile->Extent(gravity=>'West', width=>$w_new, height=>$h, background=>'transparent'); $tile->Composite(image=>$prototile_crm, 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)
- http://www.vi-anec.de/Trance-Art/IM-examples/IM-plane_group_pmm/pmm_e.pdf
- http://www.vi-anec.de/Trance-Art/IM-examples/IM-plane_group_p4m/p4m_e.pdf
- http://www.vi-anec.de/Trance-Art/IM-examples/IM-plane_group_p3m1/p3m1_ges_e.pdf, internal link
- http://www.vi-anec.de/Trance-Art/IM-examples/IM-plane_group_p6m/p6m_e.pdf
- http://www.vi-anec.de/Trance-Art/IM-examples/IM-plane_group_p3/p3_e.pdf
- http://www.vi-anec.de/Trance-Art/IM-examples/IM-plane_group_p31m/p31m_e.pdf
- G. Bachelier's evolutionary art processes (2007) with some pointers to his use of euclidean symmetry groups: Günter Bachelier: Embedding of Pixel-Based Evolutionary Algorithms in My Global Art Process. In: Romero, Juan; Machado, Penousal: The Art of Artificial Evolution. Springer, Berlin, 2007, S. 249-268. http://www.vi-anec.de/Trance-Art/AROSHU/Talks/SpringerEArtBook2006rev.pdf
- Sehnaz Cenani, Gulen Cagdas: A Shape Grammar Study: Form Generation with Geometric Islamic Patterns. In: Celestino Soddu (ed.): Generative Art 2007, X Generative Art Conference 12-14 December 2007. ISBN: 9788896610084. http://www.generativeart.com/on/cic/papersGA2007/22.pdf
- Ebru Ulu, Sinan Mert ŞENER: A SHAPE GRAMMAR MODEL TO GENERATE ISLAMIC GEOMETRIC PATTERN. In: Generative Art 2009. http://www.generativeart.com/on/cic/GA2009Papers/p25.pdf
- Ramgopal Rajagopalan, Eric Hortop, Dania El-Khechen, Cheryl Kolak Dudek, Lydia Sharman, Fred Szabo, Thomas Fevens and Sudhir Mudhur: Inference and Design in Kuba and Zillij Art with Shape Grammars. Pages 419–428 http://archive.bridgesmathart.org/2006/bridges2006-419.html http://archive.bridgesmathart.org/2006/bridges2006-419.pdf
- B. Lynn Bodner: Hankin’s ‘Polygons in Contact’ Grid Method for Recreating a Decagonal Star Polygon Design. Pages 21–28 http://archive.bridgesmathart.org/2008/bridges2008-21.html http://archive.bridgesmathart.org/2008/bridges2008-21.pdf
- Data Science Competitions: http://www.kaggle.com/competitions
- Tilings Encyclopedia (for substitution rules): http://tilings.math.uni-bielefeld.de
- Brian Wichmann: The world of Patterns. 2001. ISBN: 978-981-02-4619-8. DOI: http://dx.doi.org/10.1142/9789812839008_0001 http://www.worldscientific.com/worldscibooks/10.1142/4698#t=toc
- The Tiling Database http://www.tilingsearch.org/ with contribution of Brian Wichmann
Tiling Classification in "B. Wichmann: The world of Patterns"
Mathematical
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
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