Hacker News Reader

Comment by vaksel | Hacker News Reader

   the company’s map-making team faced a problem that even the best and brightest could not solve. 
   Maps produced by the service were taking too long to download and appear on phones. Enter Mr. Mavinkurve, who floated an     
  alternative: cut the number of colors in each map section to 20 or 40 from around 256. Mr. Mavinkurve used a rare combination of creativity, 
  analysis, engineering and an understanding of graphics to find a solution that had eluded the rest of the team."

Are you kidding me?

View on HN

It seems really strange.

But, sometimes Google engineers have huge blind spots. Often they are just general purpose smart engineering students. I've met plenty who couldn't deal with piping on the command line. It's barely plausible that nobody on the team even knew there were GIFs with smaller look-up tables, or the overhead involved in dithering or making smoother transitions.

Come to think of it, I bet this is what really happened: they were reusing map tiles from Maps and didn't even consider making their own. So, maybe this guy built a whole new tile generation pipeline for mobile, or figured out some way to remap colors from existing tiles into a smaller look-up table without sacrificing too much quality. That could be legitimately heroic.

He properly had the knowledge that the eye could not see the difference, or that the phones did not display more than 20 different colors.

But yeah that quote isn't the best.

Media always distort stories. But of course this makes you wonder how come those people can grill you during interview with all questions that you can't answer seems so imbecile.

Of course to design an algorithm to find a good smaller color depth that closes to original color depth is not an easy engineering issue. I guess it is this part that the reporter messed up the story and made it sounds so ridiculous to techies.

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.

Reply on news.ycombinator.com