r/Python • • Oct 13 '19

Made a genetic algorithm with the task of recreating an image using triangles. Used the pillow library for the image work and the rest was just math :)

Post image
946 Upvotes

78 comments sorted by

28

u/pynberfyg Oct 13 '19

What metric are you using to compare similarity?

6

u/Dirt2Master Oct 14 '19

Well, it looks at the original image as an example.

the program generates 10000 random triangles and saves their properties. then compares which one is closest to matching the sample picture.

it then saves this triangle and uses as a base for the next generation.

5

u/dzamlo Oct 14 '19

The question is how do you compute

closest to matching the sample picture.

You can use a simple sum of pixel absolute difference, but you can also use more complex metrics

4

u/Dirt2Master Oct 14 '19

pixel absolute difference is what i usef

6

u/IAmAHat_AMAA Oct 14 '19

Also you should try using a perceptually uniform colour space like CIELAB for comparisons

1

u/Coul33t Oct 14 '19 edited Oct 14 '19

lol why is this downvoted, if it not how it's currently done, this is actually a very good advice since the distance between colours in the L*a*b* space is closer to how we see it as humans than distance in the RGB space.

3

u/chronics Oct 14 '19

Could you make one using the L2 (least squares) distance? That would probably make a nice visualization of the sparsity inducing effects of the L1 distance you used.

28

u/JoseALerma Oct 13 '19

Segment image into triangles and compare average color within each triangle. When close enough, move on to the next triangle. Smaller the triangle, the greater the precision.

That would explain why the colors are similar, but the shapes are more blurry.

At least, that's my guess.

10

u/DuckSaxaphone Oct 14 '19 edited Oct 14 '19

It's reasonable but not how this is usually done with genetic algorithms.

The picture is blurry because it's made out of N triangles so you'll never get a perfect image.

The algorithm would be:

  • Generate M images with N triangles each. Each triangle should have random size, position and colour.

  • score each image by sum of absolute pixel difference

  • make a generation of M new images from the top scoring images of last generation (combine something like half the triangles from each of a random pair to make new image)

  • randomly tweak some triangles

  • repeat until average score of latest generation is very good

EDIT: Based on their other comments, it looks like OP did what you guessed. Which isn't a genetic algorithm but it's a cool result anyway.

3

u/Dirt2Master Oct 14 '19

just starting :)

6

u/pynberfyg Oct 13 '19

Sounds reasonable.

14

u/[deleted] Oct 14 '19

import Triangles

3

u/dreamin_in_space Oct 13 '19

That's the same thing I was wondering. A write up would be cool.

I did some GA TSP research back in the day. Was a lot of fun.

42

u/humanitysucks999 Oct 13 '19

"just math"

6

u/Dirt2Master Oct 14 '19

yes. practically

23

u/chunkyasparagus Oct 14 '19

2

u/H_Psi Oct 14 '19

Step 1: Draw some circles around your points

Step 2: Draw the rest of the triangulation

9

u/tian2992 Oct 14 '19

Quite cool concept, reminds me of Primitive https://github.com/fogleman/primitive

5

u/Dirt2Master Oct 14 '19

i think thats just a better version of this πŸ˜‚

Thanks for showing me , i'll see what i can use in this to improve mine.

i see this uses transparent rectangles. so :/

7

u/Steampunkery Oct 13 '19

Needs more triangles

2

u/Dirt2Master Oct 14 '19

all i have to do is let it run longer for it to look better :)

10

u/querymcsearchface Oct 13 '19

"I got a fever, and the only prescription is....more triangles!"

1

u/JanDerion47 flair=None Oct 14 '19

*Will die if no more triangles*

6

u/XxGothicfanxX Oct 13 '19

looks rad, nice

3

u/sensual_rustle Oct 14 '19

Can you output this as svg images instead so we can get scaling resolution on the images?

3

u/Dirt2Master Oct 14 '19

it doesn't exactly matter with the resolution as the image would look practically the same. Sure, i'll look into it for ya.

the only reason why the best looks so messy is i ran it for 1 night, if i ran it longer it should look better.

2

u/sensual_rustle Oct 14 '19

My understanding is svg is based on vector math. That should scale really cleanly.

I COULD be wrong, but most the companies I've been working with have been moving to svg for design images over the past few years. Seems this would be a possible cool use case

3

u/Dirt2Master Oct 14 '19

aight, will look into it :)

0

u/[deleted] Oct 14 '19

[deleted]

2

u/Dirt2Master Oct 14 '19

i actually dont know, i didnt log it :/

0

u/Dirt2Master Oct 14 '19

1 triangle is 1 generation

0

u/[deleted] Oct 14 '19

[deleted]

3

u/DangerousDoubt7 Oct 14 '19

That looks really cool.

3

u/Dirt2Master Oct 14 '19

Thanks man!

3

u/Lucarai Oct 14 '19

Upvoted for Deathstroke.

3

u/Dirt2Master Oct 14 '19

If you would like to see this on github, please dm me :)

2

u/TrainingShift3 Oct 14 '19

this is just awesome.

hope to be skilled enough to do something this cool someday

3

u/Dirt2Master Oct 14 '19

You should be! i made this after just learning python for a few weeks

2

u/[deleted] Oct 14 '19

How did you learn this/come up with this? Was it something you had seen or read about? Or what? How did you get started with something like this and even know where to begin? Just wondering. Thanks.

1

u/Dirt2Master Oct 14 '19

Well actually, i saw a project like this on scratch, so i looked at how it found out how to make an image with hexagonal shapes.

so using python, i came up with a genetic algorithm to create a new image off of a base image. Its goal is to match the sample image as best as possible so in 1 generation, it creates 10,000 random triangles, all random colors, and it chooses the triangle that best fits in the image and makes the "best image" have a value closer to the sample one. it repeats this process indefinitely

You should start by understanding what a Genetic Algorithm is. :)

4

u/DuckSaxaphone Oct 14 '19

Am I understanding correctly that you:

  • Create 10 000 random triangles

  • Choose one that best fits the image

  • Regenerate all the others

  • Repeat until convergence or you want to stop

Because that is an optimization algorithm that would get you a cool image (as can be seen in your post) but it's not really a genetic algorithm.

1

u/Dirt2Master Oct 14 '19

im pretty sure i made the program look at the best triangles color and shape, hen replicate it in the next generation with mutations, i havent looked at the code in a while as i just found out about r/python and made this program quite a while ago.

3

u/DuckSaxaphone Oct 14 '19

Ok, I'd be really interested to see your code if it's on github!

The classic way to do this problem with genetic algorithms is to treat whole images as the individuals in your population and triangles as genes (if we're doing the natural selection analogy). So you generate lots of images, keep the best x% and mix their triangles to make a new generation of images. Then repeat until you end up with a generation of images that all replicate the original.

I can see the logic of treating all your triangles as individuals and reproducing until the population as a whole best replicates the image but I think it wouldn't have the benefits of a genetic algorithm for this task.

1

u/Dirt2Master Oct 14 '19

Definitely , this was more of a test to see if i could do it so yeah.

2

u/DuckSaxaphone Oct 14 '19 edited Oct 14 '19

Totally, I don't mean to be overly critical but I thought you might be learning about genetic algorithms so I wanted to chime in.

Your result is cool and the algorithm is probably waaay more efficient than a genetic algorithm which can be very intensive to run for this problem. The upside of the GA would be that you'd be less likely to get stuck in a local minimum.

1

u/Dirt2Master Oct 14 '19

no insults taken, i have improved a lot since i created this program, this is an opportunity for me to look back and improve it :)

2

u/Epoch_Unreason Oct 14 '19

What does worst look like?

2

u/Dirt2Master Oct 14 '19

blobs of color πŸ˜‚

1

u/Dirt2Master Oct 14 '19

I released it on github: https://github.com/TyperOfCode/image_algorithm/

Feel free to use, experiment and improve the code :)

1

u/[deleted] Oct 14 '19

Cool stuff!

1

u/Dirt2Master Oct 14 '19

Thank you man!

1

u/[deleted] Oct 14 '19

Could you use this in 3D?

1

u/Dirt2Master Oct 14 '19

yes this could

1

u/SushiSuki Oct 14 '19

Is that Blade from TT?

1

u/Dirt2Master Oct 14 '19

Thats Deathstroke :)

Aka slade from teen titans, yes

1

u/SushiSuki Oct 14 '19

Oh rip yeah i meant slade! Haha

2

u/PrimaCora Oct 14 '19

I enjoy this corrupted looking art style, would love to see a game go crazy with it, or a developer go crazy trying to work with its hitbox/clipping bounds.

2

u/AVDelay Oct 14 '19

It is really cool, I would like to play with it. If you put it on github, please dm me sir.

2

u/cgw3737 Oct 14 '19

This seems like something that could be done with a genetic algorithm.

1

u/[deleted] Oct 14 '19

It'd be very interesting if you could make a fitness function for this that's not absolute error, since often in GA's we don't have the "answer" as we do in this example. For instance, if I was to add triangular noise and send you the noisy image without the target product, how do you define what's a "better" permutation of the pixels? Still very cool though, 10/10 would de-noise again!

0

u/[deleted] Oct 13 '19

[deleted]

45

u/Dirt2Master Oct 14 '19 edited Oct 14 '19

sure, i would love to upload ot on github!

just my code is not exactly viewer friendly.

Hermits nest

Edit: https://github.com/TyperOfCode/image_algorithm/

:) feel free to edit and experiment.

2

u/ceomm Oct 14 '19

I want to contribute. I have to develop similar algorithm long time ago but with convex polygons

30

u/blackerbird Oct 14 '19

No one expects it to be perfect - we would love you to share how you have done it so that we can see what was used, what you did and learn from it. People appreciate it, they won’t criticise you!

11

u/--0mn1-Qr330005-- Oct 14 '19

Yes, share the code!

6

u/Pokemon-Master-RED Oct 13 '19

I too would like to see this on a repo somewhere. Would love to toy with it.

1

u/Dirt2Master Oct 14 '19

1

u/Pokemon-Master-RED Oct 14 '19

Awesome, thank you!

I do some illustrating, so I am planning to toy with this to come up with some fun color palettes.

1

u/stermister Oct 13 '19

Is there a standard library for Genetic Algorithms? In the past I've just recreated them

6

u/Dirt2Master Oct 14 '19

no , i used no library for this.

2

u/DenormalHuman Oct 14 '19

There are several, google 'python ga library'

However, you will need then to fit with their methodology and approach to GA's as a whole.

I find the basic principles behind GA so simple that it has always been easier to knock something together from scratch than often work to rework my problem to fit with the approach of a particular library.

0

u/[deleted] Oct 14 '19

[deleted]

4

u/gunnerman2 Oct 14 '19

To be fair, this was a common assignment in the CS dept. at the school I went to. Our class got to do an adaptation of Karl Simms Evolving Virtual Creatures though, which was a lot of fun.

1

u/Dirt2Master Oct 14 '19

nah , ill post it on git

2

u/blargLeChien Oct 14 '19

yeah, I feel the same way.

I mean at this point every lineI write is in git, and I push most repo in github because why the fuck not? So why not post the link to begin with.

At the same time, I would need a non-troll reddit account before associating my github to reddit.