Friday, February 20, 2004
      ( 11:06 AM ) Matt  

Lossy PNG

PNG (Portable Network Graphic) is a lossless image compression algorithm. It is based on GIF77 (LZH) compression and Huffman trees. Basicly, the way it works is the image is serialized into a stream of values. Then the stream is written to a file, but whenever it sees a series of values which is a repeat of something that happened before, it only needs to record where the series was last seen and how long it is. (This is GIF or LZH compression.) Then, a Huffman tree is used to make the more common values in the output take up less space, and the less common values take up more space. This compresses the image a little further.

This method works really well for images like screenshots where identical colors and patterns are repeated througout the image, but when PNG is applied to digital photographs, compression is not nearly as effective. The JPG format is a lossy compression technique meaning that the compressed image is not exactly the same as the original image. The differences are chosen to make the compression more effective while making the image virtually indistinguishable from the original.

Yesterday, I was thinking about making PNG lossy so that I could compress scanned images of handwriting effectivly. So, I did a quick web search, and found someone who had already done it! His results aren't too impressive. It seems his algorithm really loses a lot of information. My guess is that when he is determining if a previous series of values is "similar enough", he is looking at the sum of the differences instead of something more meaningful like the average difference. That way, pretty much any short string would be considered "close enough" while a longer string is very unlikely to be "close enough". This would result in poor compression and poor image quality.

The neat thing about lossy PNG is that the resulting file is readable by any standard PNG viewer. (Most modern web browsers support PNG.) So, I think I might try to implement a better lossy PNG algorithm.

# -

Comments: Post a Comment

Dreams I have...

Powered by Blogger
Feel free to e-mail me.

free hit counter