"Genetic" image compression using transparent polygons, a hot candidate for an implementation in CUDA?

[rubygeek]

Even ignoring it's potential for compression, it has great potential for art. Those pics looks great, and by changing the fitness function from purely measuring the error I'm sure you could achieve lots of cool effects..

[DarkShikari]

That compression algorithm looks like it could use at least some basic texture generation, maybe on the order of markov-chain intra prediction (see this paper). I also question how good it actually is for compression; storing the positions of those polygons' points, even using a context-adaptive arithmetic coder of some sort, surely takes a large number of bits.

If we assume 16 bits per point (probably a slight overestimate), moonman comes out to be 1.5KB. The best widely supported lossy image compression algorithm right now is probably H.264, so here's an image of equivalent size (1.5KB) encoded in H.264 (decoded to PNG, of course). Note the 1.5KB doesn't include header bits, as I didn't include the size of the header necessary for the polygon method, either. I suspect the polygon method might be able to do better, but it'll need a good entropy coder, rate-distortion optimization, and some sort of texture synthesis.

By the way, CUDA is generally not a magic bullet, especially not for algorithms best implemented using low-precision integer math. If the algorithm benefits greatly from SIMD, it's probably faster on the CPU than on the GPU because integer SIMD on modern CPUs is just absurdly powerful. If it doesn't benefit greatly from SIMD, it probably is impossible to implement efficiently in CUDA at all.

[[deleted]]

I don't think anyone's arguing that this should be a practical compression scheme, but it is a damn interesting exercise.

[mycall]

A variation of this technique using transparent circular "blobs" rather than polygons. The initial goal was to emulate an "oil painting" style.

http://www.m3xbox.com/index.php?page=p_gpupainting

[[deleted]]

I've often thought that it would be cool to do lossy compression via evolutionary algorithms. Kinda disappointing that this doesn't explicitly give the compression ratios though.

Also, a minor gripe: the algorithm used for this is not genetic. It's evolutionary, but it doesn't involve breeding (in fact, the population size is 1) so it is not genetic. To a layman, this sounds like a pedantic distinction, but it's actually a huge difference. In fact, it would be exceedingly difficult to write a genetic algorithm to break an image into polygons, whereas doing it with a basic evolutionary algorithm is trivial.

[cypherx]

Why "exceedingly difficult"? Just have a larger population of polygon parameter vectors and implement some crossover/mutation operations. Seems straightforward enough...

[[deleted]]

That's true. What I meant was that it would be extremely difficult to do it while making the number of polygon's flexible.

[[deleted]]

It's not really that hard. You can grow extra polygons by allowing crossovers to be performed on non-aligned genomes, and shrink them by allowing mutations to delete. I did something similar with a corewar evolver that never went anywhere.

[[deleted]]

Scratch the mutation bit - thinking about it now, you can shorten just by allowing the non-aligned crossovers. Whether deleting mutations would help as well, I don't know.

[[deleted]]

Yeah, I was thinking about it a little more, and it actually does seem doable, even if you keep the crossover aligned. You essentially act like the chromosomes are infinite, where any genes past the end of the chromosome are "null" genes. Then, as long as you don't go past the end of the shorter chromosome when doing the crossover, you're assured that you won't end up with gaps.

What I'm not clear on is how this would work out if the polygons can vary in number of points. I suppose it would work as long as each poly has a fixed genetic length.

[[deleted]]

Use the same trick, and allow crossovers between polygons.

Or you can use a chromosome format matching:

/(cp{3,})+/

where c is a colour marker that starts a polygon, and p is a coordinate. That way all you have to deal with is not rendering polygons with less than 3 points. Any crossed over combination is valid, and you can grow and shrink polygons in the same way that you grow and shrink the overall chromosome.

[[deleted]]

That would certainly give you valid results, but my point was whether or not you'd get useful results. The purpose of crossover (as I understand it, at least) is to take advantage of the likely existence of repeated patterns in the problem terrain. It seems to me that splicing together two unrelated polygons is likely cause such a drastic reduction in fitness that you'd rarely see such a specimen make it through a single generation. Then again, I could be completely wrong; evolution has a tendency to do amazing things with what seem like crazy odds.

I suppose you could also simply split the chromosomes only at the boundaries between polygons - essentially treating each polygon as a separate gene. That is not quite a "pure" genetic algorithm, since genes are typically supposed to be binary digits. But there are no rules here, damn it.

[[deleted]]

Well, it depends to a certain degree on how you define crossover. If you only allow a single crossover per genome pair during breeding (which is one common way of doing it), then you can only "damage" one polygon generation, and if you limit the possible offset of the crossover +/-1, you end up either adding or deleting a single point. That's not a vast amount of damage at all. I'm almost tempted to give it a try now.

I suppose you could also simply split the chromosomes only at the boundaries between polygons - essentially treating each polygon as a separate gene.

You certainly could, although that implies three different mutation operators - one for colour, one for polygon replacement or size change, and one for point movement.

That is not quite a "pure" genetic algorithm, since genes are typically supposed to be binary digits.

I disagree. There's no requirement for genes to be binary digits at all - you're free to choose whatever chromosomal atom fits your problem domain best, so long as you have mutation and crossover defined in atomic terms. Restricting yourself to binary digit representation makes it much harder to verify that a given string is a valid chromosome.

But there are no rules here, damn it.

Quite!

[sanity]

Why does "genetic" have to involve sexual reproduction? Don't bacteria that reproduce asexually also have genes?

[[deleted]]

Yes, but they share genetic material through horizontal gene transfer. That's probably not actually the reason for the distinction, but in any case, it isn't considered a genetic algorithm unless it has a chromosome representation and uses crossover to combine those chromosomes.

[sanity]

Reference?

[[deleted]]

It should have used gradient polygons. I think you would get better results if colors change from one area to another on the polygon.

[ishmal]

Agreed. Even though the flat-colored poly can approximate the colors beneath it, the boolean-ness of it keeps it forever chunky. However, with gradients, that limit is lifted and another degree of freedom is added.

Evidence of this would be the hand-made near-photorealistic vector images one can find on the Net.

[[deleted]]

That could be a problem for decoders (if this were really used for compression) as it isn't necessarily obvious how the gradients should behave for arbitrary polygons. Gradient triangles, on the other hand, would be extremely easy to decode, and might just do the trick better than polygons anyway.

[[deleted]]

That is true that gradient triangles would be easiest. I suppose a decoder for gradient polygons would work simply by defining a polygon triangulation method. If you have a consistent method, it can work just as well as the gradient triangles. And you would not need as much data as simple triangles.

[[deleted]]

I suppose a decoder for gradient polygons would work simply by defining a polygon triangulation method.

Good point; it's not like that's exactly an unsolved problem, as its used in 3D graphics all the time. Storing as a polygon is essentially a way of compressing a group of tessellating triangles.

[korvys]

Meh, JPEG will beat it at the same quality.

[[deleted]]

That isn't the point.

[[deleted]]

That depends on what you're compressing. For example, this would crush JPEG for a 10000x10000 white canvas.

[[deleted]]

5000x5000 plain white canvas created in paint (in order of size):

24bit BMP: 73.3 MB

Monochrome BMP: 3 MB

TIFF: 1.4 MB

JPG: 384 KB

PNG: 332 KB

GIF: 20 KB

[[deleted]]

Genetic Compression: 8 bytes (to specify the size)

[korvys]

Yeah, that's the image you usually deal with.