The Graphics Interchange Format (GIF) was developed by CompuServe Inc., Columbus, Ohio, Usa. The GIF format was developed for fast transfer of hardware independent images at low data transfer rates. The GIF image file can store several images in one file. The images are LZW-coded and the compression rate of 50% can be achieved.
In GIF format all of the information of the image is stored; meaning that no information is lost when an image is compressed and stored into the GIF format. The color of every pixel in a GIF formatted image is coded in 8-bit value. Every value has its own entry in color table where every color has RGB (Red, Green, Blue) values. The color table has maximum of 256 entries, so the number of colors is limited to 256. The red, green and blue values in the color table are also 8-bit values. So, the syntax of the color table is the following:
7 6 5 4 3 2 1 0 Field Name Type
+===============+
0 | | Red 0 Byte
+- -+
1 | entry 0 | Green 0 Byte
+- -+
2 | | Blue 0 Byte
+- - - - - - - -+
3 | | Red 1 Byte
+- -+
| entry 1 | Green 1 Byte
+- -+
up | |
+- . . . . -+ ...
to | |
+- -+
| entry 255 | Green 255 Byte
+- -+
767 | | Blue 255 Byte
+===============+
The format of GIF file is the following:
1. File Header:
Identifier, version, screen width, screen height, bits per pixel,
backgroud color, pixel/page ratio
2. Optional RGB color table
3. Optional extension block
+-------
| 4. Image description block:
| Identifier, left border, upper border, width in pixels, height
| in pixels,...
| 5. Optional: local color table
| 6. Image data (in LZW)
| Lenght of 1. data block, 1. data block,
| Lenght of 2. data block, 2. data block,
| ...
| Lenght of n. data block, n. data block.
+-------
+-------
| 4. ...Optional 2. image
| 5. ...
| 6. ...
+-------
etc.
The complete definition of GIF format is descriped in a document by CompuServe Incorporated (http://www.soften.ktu.lt/~marius/docs/graph/gif89a.doc)
If the colors of the palette can be divided in pairs of almost equal appearance, one color in each pair can be used to code bit value 0 and the other to code 1. In the hiding pixels, one then uses the secret bit value to decide which color from the pair should be chosen.
[Sandford & al.] suggest an algorithm for pairing the colors. Their strategy is to take one arbitrarily chosen color at a time and to find the closest matching pair for it. Both colors are removed from the set of available colors before arbitrarily choosing the next color for pairing. The matching is based on the hue of the color in the HSI system. Maximum limits are also given for differences in hue and intensity. This heuristic will find reasonably good pairs, but it is not guaranteed to produce in any way optimal results.
As our first approach, we have chosen a sligtly more conservative algorithm. We start by finding the closest match for each color by computing the Euclidian distances between the RGB coordinates. Only colors that both have each other as the closest match will be accepted for pairs. Also, we will have an upper limit for the coordinate distances. Some colors may not be be part of any pair and pixels with these colors should reamain unchanged in the image.
It is easy to later experiment with the HSI system and alternative pairing algorithms. For example, it is possible to find the maximum number of pairs meeting some criterion.