From Daan
MeesterDaan (talk | contribs) |
MeesterDaan (talk | contribs) (→Paintings) |
||
| (29 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | This page is dedicated to the EVOSTAR' | + | This page is dedicated to the EVOSTAR'19 publication "Paintings, Polygons and Plant Propagation". |
| Line 14: | Line 14: | ||
!Bach | !Bach | ||
|- | |- | ||
| − | |valign="top" |[[Image:180x240MonaLisa.png|frame|Mona Lisa (1503) by Leonardo da Vinci]] | + | |valign="top" |[[Image:180x240MonaLisa.png|frame|Mona Lisa (1503) by Leonardo da Vinci.]] |
|valign="top" |[[Image:180x240Mondriaan.png|frame|Composition with Red, Yellow and Blue (1930) by Piet Mondriaan.]] | |valign="top" |[[Image:180x240Mondriaan.png|frame|Composition with Red, Yellow and Blue (1930) by Piet Mondriaan.]] | ||
| − | |valign="top" |[[Image:180x240Klimt.png|frame|The Kiss (1908) by Gustav Klimt]] | + | |valign="top" |[[Image:180x240Klimt.png|frame|The Kiss (1908) by Gustav Klimt.]] |
|valign="top" |[[Image:180x240Bach.png|frame|Portrait of Johann Sebastian Bach (1746) by Elias Gottlieb Haussman.]] | |valign="top" |[[Image:180x240Bach.png|frame|Portrait of Johann Sebastian Bach (1746) by Elias Gottlieb Haussman.]] | ||
|} | |} | ||
| Line 27: | Line 27: | ||
!Starry Night | !Starry Night | ||
|- | |- | ||
| − | |valign="top" |[[Image: | + | |valign="top" |[[Image:240x180StarryNight.png|frame|The Starry Night (1889) by Vincent Van Gogh.]] |
|valign="top" |[[Image:240x180JacksonPollock.png|frame|Convergence (1952) by Jackson Pollock.]] | |valign="top" |[[Image:240x180JacksonPollock.png|frame|Convergence (1952) by Jackson Pollock.]] | ||
| − | |valign="top" |[[Image: | + | |valign="top" |[[Image:240x180Dali.png|frame|The Persistence of Memory (1931) by Salvador Dali.]] |
|} | |} | ||
</Center> | </Center> | ||
| Line 62: | Line 62: | ||
<Center> | <Center> | ||
| − | {|class="wikitable" | + | {|class="wikitable"| align="center" | style=" align="center"; text-align: center; margin-left: 1em; margin-bottom: 1em; font-size: 100%;" |
|- | |- | ||
| − | | colspan="3" |[[Image:180x240MonaLisaPoly.png|Mona Lisa (1503) by Leonardo da Vinci]] | + | | colspan="3" |[[Image:180x240MonaLisaPoly.png|frame|Mona Lisa (1503) by Leonardo da Vinci. (Done with Simulated Annealing)]] |
| − | | colspan="3" |[[Image:180x240MondriaanPoly.png|Composition with Red, Yellow and Blue (1930) by Piet Mondriaan.]] | + | | colspan="3" |[[Image:180x240MondriaanPoly.png|frame|Composition with Red, Yellow and Blue (1930) by Piet Mondriaan. (Done with Hillclimber)]] |
| − | | colspan="3" |[[Image:180x240KlimtPoly.png| | + | | colspan="3" |[[Image:180x240KlimtPoly.png|frame|The Kiss (1908) by Gustav Klimt. (Done with Plant Propagation)]] |
| − | | colspan="3" |[[Image:180x240BachPoly.png|Portrait of Johann Sebastian Bach (1746) by Elias Gottlieb Haussman.]] | + | | colspan="3" |[[Image:180x240BachPoly.png|frame|Portrait of Johann Sebastian Bach (1746) by Elias Gottlieb Haussman. (Done with Hillclimber)]] |
|} | |} | ||
</Center> | </Center> | ||
| + | |||
<Center> | <Center> | ||
| − | {|class="wikitable" | + | {|class="wikitable"| align="center" | style=" align="center"; text-align: center; margin-left: 1em; margin-bottom: 1em; font-size: 100%;" |
|- | |- | ||
| − | | colspan="4" |[[Image: | + | | colspan="4" |[[Image:240x180StarryNightPoly.png|frame|The Starry Night (1889) by Vincent Van Gogh. (Done with Plant Propagation)]] |
| − | | colspan="4" |[[Image:240x180JacksonPollockPoly.png|Convergence (1952) by Jackson Pollock.]] | + | | colspan="4" |[[Image:240x180JacksonPollockPoly.png|frame|Convergence (1952) by Jackson Pollock. (Simulated Annealing)]] |
| − | | colspan="4" |[[Image: | + | | colspan="4" |[[Image:240x180DaliPoly.png|frame|The Persistence of Memory (1931) by Salvador Dali. (Done with Hillclimber)]] |
| + | |} | ||
| + | </Center> | ||
| + | |||
| + | ==New Paintings== | ||
| + | |||
| + | <Center> | ||
| + | {| align="center" | style=" align="center"; text-align: center; margin-left: 1em; margin-bottom: 1em; font-size: 100%;" | ||
| + | !Salvator | ||
| + | !Lady Ermine | ||
| + | |- | ||
| + | |valign="top" |[[Image:180x240SalvatorMundi.png|frame|Salvator Mundi (1503) by Leonardo da Vinci.]] | ||
| + | |valign="top" |[[Image:180x240LadyErmine.png|frame|Lady with an Ermine (1490) by Leonardo da Vinci.]] | ||
|} | |} | ||
</Center> | </Center> | ||
| + | ==Resources & Media== | ||
| + | |||
| + | A [https://www.youtube.com/watch?v=u91gRGY8ElQ movie clip] of the algorithm at work. | ||
| + | |||
| + | |||
| + | * [graph typicalruns][graph best end results][link to data records] ... available on request. | ||
| + | |||
| + | * Here's our [http://heuristieken.nl/resources/PaintingsFromPolygons.zip source code]. | ||
| + | |||
| + | |||
| + | ==Errata== | ||
| + | * In equation (7), the factor (1−fi) should be just (fi). The typo is just in the paper, not in the source code, and therefore doesn't affect the results (see organisms.py, line 138). | ||
| + | * In equation (9), the factor 9v/4 is incorrect; the experiments were done with 13v/5. The factor 1/nmax from the same formula was never in the experiment (see organisms.py, line 143). It is most likely a uncorrected textual remnant from an earlier probe. In general, we have been looking for a good way to transfer the PPA-algorithm to this problem, and many adaptations are possible. | ||
| − | |||
| + | ==Misc== | ||
| − | + | * A simplified version of the problem was proven to be [http://heuristieken.nl/resources/(2020)VandenBerg-SimplifiedPaintingsfromPolygonsisNPHard.pdf NP-hard] in 2020. | |
| − | [ | + | * We got simulated annealing to work in a [http://heuristieken.nl/resources/(2020)Dahmanietal-PFPSimulatedAnnealing.pdf paper] published at ICCC'20. |
Latest revision as of 11:49, 7 June 2021
This page is dedicated to the EVOSTAR'19 publication "Paintings, Polygons and Plant Propagation".
Paintings
These are the target bitmaps used in our experimental runs.
| Mona Lisa | Mondriaan | Klimt | Bach |
|---|---|---|---|
 Mona Lisa (1503) by Leonardo da Vinci. |
 Composition with Red, Yellow and Blue (1930) by Piet Mondriaan. |
 The Kiss (1908) by Gustav Klimt. |
 Portrait of Johann Sebastian Bach (1746) by Elias Gottlieb Haussman. |
| Dali | Jackson Pollock | Starry Night |
|---|---|---|
 The Starry Night (1889) by Vincent Van Gogh. |
 Convergence (1952) by Jackson Pollock. |
 The Persistence of Memory (1931) by Salvador Dali. |
Painting provenance (recovered 31-9-2018):
BACH: Wikipedia, Public Domain (https://en.wikipedia.org/wiki/Johann_Sebastian_Bach)
DALI: Wikiart, Fair Use (https://www.wikiart.org/en/salvador-dali/the-persistence-of-memory-1931)
MONA LISA: https://www.wikiart.org/en/leonardo-da-vinci/mona-lisa
MONDRIAAN: https://www.wikiart.org/en/piet-mondrian/composition-with-red-blue-and-yellow-1930
POLLOCK: https://www.wikiart.org/en/jackson-pollock/convergence-1952
STARRY NIGHT: https://www.wikiart.org/en/vincent-van-gogh/the-starry-night-1889
KLIMT: https://www.wikiart.org/en/gustav-klimt/the-kiss-1908
Get all the painting bitmaps in one zip file.
PolygonConstellation
These are the constellations from our last figure:
 Mona Lisa (1503) by Leonardo da Vinci. (Done with Simulated Annealing) |
 Composition with Red, Yellow and Blue (1930) by Piet Mondriaan. (Done with Hillclimber) |
 The Kiss (1908) by Gustav Klimt. (Done with Plant Propagation) |
 Portrait of Johann Sebastian Bach (1746) by Elias Gottlieb Haussman. (Done with Hillclimber) |
 The Starry Night (1889) by Vincent Van Gogh. (Done with Plant Propagation) |
 Convergence (1952) by Jackson Pollock. (Simulated Annealing) |
 The Persistence of Memory (1931) by Salvador Dali. (Done with Hillclimber) |
New Paintings
| Salvator | Lady Ermine |
|---|---|
 Salvator Mundi (1503) by Leonardo da Vinci. |
 Lady with an Ermine (1490) by Leonardo da Vinci. |
Resources & Media
A movie clip of the algorithm at work.
- [graph typicalruns][graph best end results][link to data records] ... available on request.
- Here's our source code.
Errata
- In equation (7), the factor (1−fi) should be just (fi). The typo is just in the paper, not in the source code, and therefore doesn't affect the results (see organisms.py, line 138).
- In equation (9), the factor 9v/4 is incorrect; the experiments were done with 13v/5. The factor 1/nmax from the same formula was never in the experiment (see organisms.py, line 143). It is most likely a uncorrected textual remnant from an earlier probe. In general, we have been looking for a good way to transfer the PPA-algorithm to this problem, and many adaptations are possible.
Misc
- A simplified version of the problem was proven to be NP-hard in 2020.
- We got simulated annealing to work in a paper published at ICCC'20.