Slashdot Mirror
Breakthrough In JPEG Compression
Kris_J writes "The makers of the (classic) compression package Stuffit have written a program that can compress JPGs by roughly 30%. This isn't the raw image to JPG compression, this is lossless compression applied to the JPG file. Typical compression rates for JPGs are 2% to -1%. If you read the whitepaper (PDF), they are even proposing a new image format; StuffIt Image Format (SIF). Now I just need someone to write a SIF compressor for my old Kodak DC260."
Maybe, but StuffIt is an archival program. If I have 10gb of existing jpgs and want to archive them, then this is whats wanted. Reencoding them as you suggest would be equivalent to converting say an mp3 to ogg format - a surefire way to lose quality with little gain.
Re fractal compression, people have been hyping it up for years but as far as I know it never really delivered. I'm dubious about any claims to some mysterious program which compresses anything amazingly well without strong evidence.
Wavelet compression however is used in jpeg2000 which is a bit better than jpeg but even that isn't supported by any digital cameras.
If StuffIt really does compress jpegs 25-30% that is a massive leap forward over the previous state-of-the-art compressors which reached I think around 3-4% - http://www.maximumcompression.com/data/jpg.php . Heres hoping their claims pan out, and that they release at least some details regarding the methods they used.
For those mathematically interested fractal compression tries to find a matrix transform (A) so the serie x_n = A * x_{n - 1} converges where x is an image matrix and x_{\infty}=image to compress is a fixed point.
Currently, the fastest continuous shooting digital camera (the Nikon D2X) can only take 4 shots in a row before its memory buffers get full and the whole camera becomes useless
I beg your pardon? Just about every digital SLR on the market is able to handle more than 4 images in buffer at a time. My year and a half old 10D can buffer 9 RAW images, and the D70 processes JPEGs before they hit the buffer, so it can buffer JPEGs in the dozens.
I doubt this is intended for any use other than archiving of images, where it will kick ass. It's clearly processor-intensive from the timing results, but for long-term storage that makes little difference.
I've got a few TB of images in storage and I'd love to be able to save 20-30% of that space, regardless of how cheap it is. That means a little longer between burning DVDs, and having more stuff on mounted drives for reference.
Recursive: Adj. See Recursive.
JPEG does not use Run-length encoding as its last compression step. Quote from the faq:"The JPEG spec defines two different "back end" modules for the final output of compressed data: either Huffman coding or arithmetic coding is allowed." http://www.faqs.org/faqs/jpeg-faq/part1/section-18 .html
It goes on to say that arithmetic coding is ~10% smaller, but is patented, so don't use it.
So what they are doing is removing the known chubby huffman coding and replacing it.
wikipedia
http://en.wikipedia.org/wiki/Fractal_compression
Some sourceforge projects
http://sourceforge.net/projects/mpdslow/
http://sourceforge.net/projects/fractcompr/
for audio
http://sourceforge.net/projects/fraucomp/
The original JPEG compression algorithm had Huffmann coding for the DCT variables, but it also had some fixed-length codes for the beginning and end of blocks. If you set your compression at about 10x then you can hardly see the difference with real images. bring it up to 15x and the changes are still modest. However, yank it much over about 22x, and the image will go to hell. The reason is the block handling codes meant that a JPEG image with no data at all - a flat tint - would only compress at about 64x, so at 22x compression these block handling codes are about 1/3 of your overall code. The fractional bit wastage you get with using Huffmannn coding instead of arithmetic coding mops up some of the rest as you are usig shorter Huffmann codes. The codes are also very regular, as about 1/3 of the code is not particularly random. The 1/3 figure also matches the 30% compression figures too, which isn't surprising.
Why didn't the original JPEG developers make a better job of this? Well, doing an experimental DCT compression used to take me hours or days when I was developing on a shared PDP-11, and there was always the worry that a dropped bit would lose your place in the code, and scramble the rest of the image. A little regular overhead was also useful for things like progressive JPEG control. I guess we all knew it was not as tight as things could have been, but it got the job done. We knew if you want to get 40x compression, then reducing your image to half size, and the compressing that by x10 will look better. Unfortunately, people who just drag a slider to get more compression don't always know that.
The right solution would be to use JPEG2000 which has a much smaller block overhead, and so fails much more gracefully at higher compressions.
If you're RMS, you probably believe that no one has the right to own anything and all inventions and ideas belong to the public,
Nonsense, RMS has never said that. Please read a more widely before making such malicious accusations again. Don't buy into M$ marketing smear and FUD campaign.
---
It's wrong that an intellectual property creator should not be rewarded for their work.
It's equally wrong that an IP creator should be rewarded too many times for the one piece of work, for exactly the same reasons.
Reform IP law and stop the M$/RIAA abuse.
It certainly seems possible, except for patent issues.
The heart of JPG is the DCT transform, performed on an 8x8 block basis. This is not being changed, since they claim that the original JPG can be reconstructed bit-for-bit exact. Hence their algorithm must be "lossless." Othewise, if you apply lossy compression to lossy compression, you get even more loss.
Here is the JPEG algorithm in a nutshell...
1) Convert RGB into Brightness, Color, and Saturation (three separate monochrome images).
2) Down-sample the Color and Saturation images. (This reduces the image size by 1/2; VERY lossy but you don't notice it)
3) Break each image into 8x8 blocks.
4) Perform a 2D DCT (discrete cosine transform) on each 8x8 block separately.
5) Quantize the DCT data using the special JPEG quantizaion matrix (this is where most of the loss happens)
6) Convert each 8x8 block of DCT data into a 64-number stream using the zig-zag scan (this just shuffles the order of the data, nothing more).
7) Apply a specialiazed huffman code to compress the data (lossless compression).
8) Write the header information, and dump encoded data to the file
I could be waaaay off-base on this, but I suspect that they have found a better replacement for the zig-zag scan and huffman coding steps. Optimizing another step would still be lossy, and could not re-create the original JPEG byte-for-byte.
But I must admit that I am completely baffled how they could take a huffman code optimized for JPEG and find something 30% better. Such a thing seems to be impossible, given what I know of coding theory (which, I admit, is a but rusty).
"-1 Troll" is the apparently the same as "-1 I disagree with you."