7

Image mosaics use a set of predefined squared images to build a larger image (example here). There are a lot of solutions and it's quite trivial to achieve this effect. However, it becomes much harder with the following constraints:

  1. The shape of the original mosaics is abstract. Any convex polygon could do.
  2. Each mosaic can only be used once.
  3. There is no need for the mosaics to be absolutely packed (i.e. occupying 100% of the canvas), but they should be as packed as possible without overlapping.

I'm trying to automatize the ancient art of tesselation, specifically the Opus palladianum technique.

My idea is to use simulated annealing or some other heuristic to optimize the position and rotation of each irregular mosaic, swaping two in each iteration, trying to minimize some energy function that reflects the similarity to the target image as well as the "packness" of the tiles. I'm trying to achieve this in python, any ideas and help would be greatly appreciated.

Example:

enter image description here

acdr
  • 4,538
  • 2
  • 19
  • 45
Anoyz
  • 7,431
  • 3
  • 30
  • 35
  • 2
    What do you have so far? An implementation of simulated annealing? A fitness function? – acdr Jun 30 '17 at 12:20
  • 2
    [If you have a problem with your *simulated annealing* implementation, come back with a specific question about it](https://meta.stackoverflow.com/a/334823/176769). I believe questions fishing for ideas on how to solve a problem are simply too broad to be answered. But it's totally fine to [go the Chat](https://chat.stackoverflow.com/) and talk to the people about it. – karlphillip Jun 30 '17 at 18:31
  • Instead of using "predefined shapes" it would much easier of "cutting" a final image (like Voronoi) to create those shapes. – user1767754 Jul 02 '17 at 11:51
  • @acdr I'm still outlining an algorithm. It's easy to implement an SA ou a GA, my big issue here is really finding the best strategy to solve the problem. – Anoyz Jul 07 '17 at 08:59
  • @karlphillip It's not homework, I'm way past that (senior SE here). It's a personal art project of mine. I want to shatter many [Portuguese tiles](https://www.google.pt/search?q=azulejo+portugues&source=lnms&tbm=isch&sa=X&ved=0ahUKEwjjm6Cv5vbUAhUGzRQKHeqGDycQ_AUICigB&biw=1163&bih=537) to make an image mosaic. I really just need a direction here, like someone saying this is the X type of problem and should be solved with Y approach. – Anoyz Jul 07 '17 at 08:59
  • @user1767754 No, I don't really have control over the initial pieces. For the sake of the problem one should assume they're random convex. – Anoyz Jul 07 '17 at 08:59
  • There is tools like Houdini, which u can do this probably in an hour. – user1767754 Jul 07 '17 at 10:54
  • @user1767754 You mean Houdini, the 3D modeling software? – Anoyz Jul 08 '17 at 17:02
  • Yes, but it is more a FX Software than a 3D-Modelling tool, even you can do Modelling, it is more known for it's procedural 3D Generation approaches and visual effects. – user1767754 Jul 08 '17 at 20:24

1 Answers1

3

I expect that you may probably use GA (Genetic Algorithm) with a "non-overlapping" constraint to do this job.

Parameters for individual (each convex polygon) are:

  • initial position
  • rotation
  • (size ?)

And your fit function will be build to give best note to each individual when polygon are not overlapping (and close to other individual)

You may see this video and this one as example.

Regards

A. STEFANI
  • 6,707
  • 1
  • 23
  • 48
  • Add: Depending of how many convex polygons will be used to compose your final mozaic, you may also evaluate position(&rotation) brut-forcing, or Morris Screening Test as alternative, but maybe Genetic Algorithm is best. – A. STEFANI Jun 30 '17 at 15:23
  • What about the initialization? Should I just randomly place the tiles? What's the mutation here? Swaping two tiles, or changing one's position/rotation? Also, this doesn't deal with the packing issue: there should be a way to value increases in packing. – Anoyz Jul 07 '17 at 09:02