[byrandomby1]

I need to compress (reduce size) a gif image to as small as possible.
I will only need to use the compressed file to compare it with another gif, meaning it need not retain its format or be decompressed, but just a unique identifier of the image.

For example,
I have a huge list of compress gif images.
I can then take an uncompressed gif image, compress it, and compare (the bytes) with the list of compressed ones, to find whether there is a match (duplicate).
(I can just use and compare uncompressed images but it takes too much disk space)

What I've tried:
- Compressing the bytes using GZipStream. - doesn't seem to reduce the file size
- Converting to jpg with lower quality - reduces size from ~2kb to ~1kb (not enough) even with very low quality

How can I do this?

This post has been edited by byrandomby1: 21 September 2012 - 08:22 AM

[modi123_1]

Odd thought - not all compression algorithms are the same, right? That means unless you compress your normal gif the same way as the compressed one was the byte information will be off anyways.

[byrandomby1]

modi123_1, on 21 September 2012 - 08:20 AM, said:

Odd thought - not all compression algorithms are the same, right? That means unless you compress your normal gif the same way as the compressed one was the byte information will be off anyways.

I would be using the same compression method to compare. Why wouldn't I?

[RudiVisser]

You say it doesn't need to be decompressed again, but you're also saying you want to do a byte-by-byte comparison?

Why not just use a hash? An MD5 hash would be more than sufficient for comparison of contents provided the 2 GIFs were initially encoded the same.

The problem is that you couldn't do this based *just* on contents of the file. I mean, you couldn't tell the actual difference, only that there was a difference. By compressing it further than GIFs are already compressed (which they are, GIF images aren't raw image data), you could compress the same image twice using slightly varying levels of encryption (despite being the same method!) and get entirely different results.

This post has been edited by RudiVisser: 21 September 2012 - 08:24 AM

[modi123_1]

... because you are asking for a compression algorithm. If you are asking for an algorithm then it would be sensible to believe you don't know what algorithm the compressed gifs were compressed by.

Quote

I need to compress (reduce size) a gif image to as small as possible.

[Skydiver]

Short answer: Don't compress. Use MD5 hashes (or some other hash function).

Long answer:
Do you want to compare the two GIF files or the images contained within the two files?

If you want to compare the two GIF files, just treat them as any old random file and compare the two of them. Why incur the computation and I/O overhead of compressing the two files, and then comparing the two compressed files? If the argument is that it is faster to compare 2 1MB files than to compare 2 4MB files, consider the amount of time it took to compress those two 4MB files to become 1MB files.

If you want to compare the images contained within the two files, a quick way is to first read the image dimensions from each of the two files. This will only be at around 8 bytes to be read from each file. If the two dimensions are different, then you obviously have two different images.

Text is spoiler is if you want to make some assumptions about how the data was encoded.

Spoiler

Next if the dimensions are the same, read in the color tables from each file. If present, each color table will be 256 bytes if I recall the format correctly. If the two color tables are different, again you have different images.

If the color tables are the same, or the file has no color table, only then do start comparing the pixel data stream. At this point I think that you are forced to decompress the data stream, but there is no need to actually write to disk. Just keep decompressing the streams from both files. If you get mismatched data between the streams then the images are different and you are done. If you make it to the end, then you can conclude that the images are the same.

This may seem more work, but LZW was designed to decompress very very quickly and easily. The computation overhead is much less than trying to compress a file, and as I recall, the I/O overhead of decompressing is also very low because you always move forward through a stream of data with no need for large lookahead buffers.

Why compare the output of the streams instead of the raw compressed streams? Unless you know that exactly the same LZW implementation was used to compress the data, there maybe some variances on how each different implementor may have store the compressed data, but the output data should still be the same since LZW is a lossless image compression algorithm.

A slight note on implemenations now that I'm thinking about it. Even comparing just the output of the decompressed data may have its pitfalls. It maybe possible that one GIF encoder may decide to store the image interlaced, while another implementor stores data non-interlaced, while yet another decides to partition the data in blocks. Or one may decide to order their color table is ascending frequency, while lists colors as they are found in the image.

This leads to the only true way to see if two images are the same is to actually render the data into virtual canvases, and then do pixel by pixel comparisons between the canvases. The pixel by pixel comparison should be fine if you only ever need to compare just two images.

If on the other hand, you need to compare multiple files or multiple images, then it may make sense to build a database of MD5 hashes (or whatever other hash algorithm you prefer). The hash values you get from either the file bits or the pixel data will be a much more compact way to compare files or images.

[byrandomby1]

MD5 hash seems to do the trick.
Thanks for the help.