It may not be easy but it's a well known problem. I seriously doubt they did it from scratch.

I guess the problem to is to do it without human assistance. Do you know any related research on this area? I am actually don't know where to start. And they probably want to design the solution to integrate with google's scale nothing infrastructure.

You have to find a limited number of colors that mostly approximates the original, to the human eye. This is how every GIF encoder works. Maybe there is something about your question that I am missing?

http://en.wikipedia.org/wiki/Color_quantization

I don't know what you mean by adapting it to Google's infrastructure. I think you meant to say "shared nothing". Tile serving is perfectly suited to such an architecture already. There's no shared state across tiles, for instance.

I doubt naive gif encoder will do the job.

in http://en.wikipedia.org/wiki/Graphics_Interchange_Format it mentions:

"The algorithms used to select the palette and to perform the dithering vary widely in output quality. Additionally, dithering significantly reduces the image's compressibility and thus works contrary to GIF's main purpose."

So to goal is to get the best color palette that satisfies

1. The resulting image quality is close to original image,

2. The compressed image has to be smaller than original

3. The color quantization can be automated without too much human supervision.

I think the general color quantization algorithms may solve the point 1 and 3 but not necessary point 2.

Never mind, I am an idiot sometime.