[Solved]: How can GIF compression be lossless if the maximum # of colors is 256?

Problem Detail: 

I'm reading "Computer Science Made Simple" by V. Anton Spraul, and in the chapter about Graphics, he describes GIF files as follows:

A GIF file uses lossless compression to store an image with a maximum of 256 different colors.

The way I read this, it sounds like the book is saying it stores the image, but the stored image will have a maximum of 256 colors. If this interpretation is incorrect, and the author means that the GIF format only works with original images that have a max of 256 colors, then let me know since this makes my question redundant.

With that out of the way, let's assume the following scenario:

1) I have an arbitrary image with more than 256 colors.
2) I open the file in Photoshop or some other advanced image editor.
3) I save it as a GIF.

My question is, wouldn't this result in a loss of information, or artifacts in the new GIF? I'm capped at 256 colors when using the GIF format, and therefore would lose data, right?

Asked By : Richie Thomas

Answered By : David Richerby

GIF is only capable of storing images with at most 256 different colours. If you have such an image, the compression used by GIF is lossless. If you have an image with more than 256 different colours, you must first reduce the number of colours, which does indeed lose data but that's a preprocessing stage that isn't part of the compression process. Once you've preprocessed, the compression occurs without further loss.

You should parse the sentence quoted in the question as "If you have an image with at most 256 colours, GIF will compress it losslessly", rather than "If you have an image, GIF will losslessly produce a compressed version with at most 256 colours."

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35885